On the Expressiveness of Links in Hypertext Systems
The Computer Journal, 41 (7):
459-473 (1998)Abstract
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.
Description
dret'd bibliography
