The Setting
A machine with logarithmic work space cannot store the path from the root of a tree to the node it is visiting, yet it can walk around the tree’s contour. It keeps only the current node and a counter over that node’s children, and each step descends into a child, moves the counter on, or climbs back to the parent. Such walks run inside reversible small-space computations, where every step forward must be undone by a step back computed from the same local data. The question is whether the step back does undo the step forward, and whether the walk started at a root passes through every position of the root’s tree and comes back to where it began.
Indexed Forests
A node is a pair of natural numbers, and its label is its first coordinate, .✦
An indexed forest consists of a finite set of nodes, a breadth function , a parent map that gives each node at most one parent node, and a child map that gives each node and index at most one child node , such that, with the breadth of a node , parents and children agree on : for all nodes and every index , (1)✦
A root of is a node of with no parent. A node descends from a node in generations when there are nodes of with for every .✦
The Contour Walk
An incidence of is a pair of a node and a counter ✦; it is live when and .✦ An incidence lies in the tree of a node when it is live and descends from in some number of generations.✦
The contour successor of is the map on incidences given by (2)✦
The contour predecessor of is the map on incidences given by (3)✦
For a map from a set to itself, is its -fold iterate, with the identity✦, and is reached from under , written , when for some .✦
The Claim
Theorem 1. Let be an indexed forest with contour successor and contour predecessor . If is a live incidence of , then is live and (4)✦ If is a root of , then every incidence in the tree of satisfies (5)✦ and there is an with (6)✦
In the paper, the result reads: for a finite deterministic graph as in Lemma 11.4 with a canonical success halt, the undirected component is a tree directed toward the halt, and there are mutually inverse next-mark and previous-mark operations on its contour, whose marks are the root sentinel and one occurrence of each canonical initiation, and these operations need only the current program state and bounded incidence control.
What Is Checked
The claim is stated over an indexed forest whose parent and child maps agree as in (1), over its contour successor (2) and contour predecessor (3) on incidences, and over live incidences, the trees of its roots and the iterates of .