On the Expressiveness of Links in Hypertext Systems
Luc Moreau · The Computer Journal · 1998
In this paper, we study how linking mechanisms contribute to the expressiveness of hypertext systems. For this purpose, we formalise 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 allow us to compare embedded vs separate links and simple vs generic links. Then, we investigate history mechanisms, adaptive hypertexts, and functional links. Our conclusion is that simple links, whether embeded or separate, generic links, and some adaptive links all give hypertext systems the power of finite state automata. The history mechanism confers them the power of pushdown automata, whereas the general functional links give them Turing completeness.