Martin Hofmann and Ulrich Schöpp (2009)

# Pointer Programs and Undirected Reachability

In: LICS, pp. 133-142.

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 forall-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 LOGSPACEalgorithm 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.

Artikelaktionen