We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs 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). Starting from pure pointer programs, in which only abstract pointers without any internal structure are allowed, we consider pointer programs with constructs for iterating over the input structure and for counting. We classify with which of these constructs it is possible to write a program for solving s-t-reachability in undirected graphs. The main result of this paper is a new lower bound on undirected s-t-reachability. We show that while pointer programs with counting can decide this problem using Reingold's algorithm, the problem cannot be decided by pointer programs with iteration. As a corollary we obtain that Deterministic Transitive Closure logic on locally ordered graphs cannot express undirected s-t-reachability.

We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs 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). Starting from pure pointer programs, in which only abstract pointers without any internal structure are allowed, we consider pointer programs with constructs for iterating over the input structure and for counting. We classify with which of these constructs it is possible to write a program for solving s-t-reachability in undirected graphs.

The main result of this paper is a new lower bound on undirected s-t-reachability. We show that while pointer programs with counting can decide this problem using Reingold's algorithm, the problem cannot be decided by pointer programs with iteration. As a corollary we obtain that Deterministic Transitive Closure logic on locally ordered graphs cannot express undirected s-t-reachability.