On the Expressiveness of Links in Hypertext Systems

Luc Moreau, Wendy Hall

Luc Moreau, Wendy Hall, On the Expressiveness of Links in Hypertext Systems, The Computer Journal, 41(7):459-473, 1998.

In this paper, we study how linking mechanisms contribute to the expressiveness of hypertext systems. For this purpose, we formalize hypertext systems as abstract machines. As the primary benefit of hypertext systems is to be able to read documents non-linearly, their expressiveness is defined in terms of the ability to follow links. Then, we classify hypertext systems according to the power of the underlying automaton. The model allows us to compare embedded versus separate links and simple versus generic links. Then, we investigate history mechanisms, adaptive hypertexts and functional links. Our conclusion is that simple links, whether embedded or separate, generic links and some adaptive links all give hypertext systems the power of finite state automata. The history mechanism confers to them the power of pushdown automata, whereas the general functional links give them Turing completeness.


Bibliography Navigation: Reference List; Author Index; Title Index; Keyword Index

Generated by sharef2html on 2011-04-15, 02:00:41.