Hypertext document traversal

Traversal of a graph is analogous to `browsing' or `navigating' in the World Wide Web. The user decides at which page to start and where to finish; if he knows the absolute address of a given page, he may jump directly to this page. But if not, the structure of links within a document and a system of documents which form a hypertext determines how it may be traversed, given a starting point:

1. Tree with tree-structured Contents index: arbitrary jumps within the tree are possible.
2. Tree with no index: one consistent strategy would be left-right depth-first traversal to some depth (A* traversal), that is: start at the top, take the leftmost child node, from here take the leftmost child node, and so on, until a leaf of the tree or the maximum defined depth is reached; then backtrack to the parent, take the next node, and continue the left-right, depth-first strategy from there.
3. This strategy may be used as a basis for defining Traversal Links between pages: the notion of Next may means the next item in a left-right depth-first traversal strategy; Previous may be the inverse of Next.
4. Combined Contents indexing and Traversal indexing may be used, with a jumpto the Contents index included in every page. This is the linking strategy used in latex2html, for example.
5. Other indexing strategies are possible, as a glance at different indices in books shows.
6. Dynamic indexing: a browser will generally keep a history stack of pointers to nodes in the order in which they were actually visited. This will be a mirror of the link structure if a simple traversal linking system is used. However, if a mixture of traversal strategies (for instance via a Contents index and via another traversal strategy, then the path actually taken may not reflect the structure of any one strategy.
7. If a document structure is not a tree but a general graph, then some documents will be pointed to by more than one other document. From the document concerned it will not be clear what the `previous' document was, but the `heuristic' for deciding this question is the history stack, which shows precisely from which document a given document was in fact reached.

Tasks:

1. Think of tree diagrammes in linguistic structural descriptions. How would a diagramme of a hypertext resemble one of these?
2. Think of the attribute-value structures in the HPSG or in DATR (if you know them). Could you use them to describe a hypertext?
3. What would `nodes', `edges', and `node labels' and `edge labels' correspond to in a hypertext?