Pointer Programs and Undirected Reachability
Martin O. Hofmann, Ulrich Schöpp · 2009
Pointer programs are a model of structured computation within LOGSPACE. They capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the graph nodes). In this paper we study undirected s-t-reachability for a class of pure pointer programs in which one can work with a constant number of abstract pointers, but not with arbitrary data, such as memory registers of logarithmic size. In earlier work we have formalised this class as a programming language PURPLE that features a for all-loop for iterating over the input structure and thus subsumes other formalisations of pure pointer programs, such as Jumping Automata on Graphs JAGs and Deterministic Transitive Closure logic (DTC-logic) for locally ordered graphs. In this paper we show that PURPLE cannot decide undirected s-t-reachability, even though there does exist a LOGSPACE-algorithm for this problem by Reingold's theorem. As a corollary we obtain that DTC-logic for locally ordered graphs cannot express undirected s-t-reachability.