Martin Hofmann and Ulrich Schöpp (2008)

# Pure Pointer Programs with Iteration

In: Computer Science Logic, 22nd International Workshop, CSL 2008, 17th Annual Conference of the EACSL, Bertinoro, Italy, September 16-19, 2008. Proceedings, ed. by Michael Kaminski and Simone Martini, vol. 5213, pp. 79-93, Springer. Lecture Notes in Computer Science (ISBN: 978-3-540-87530-7).

Many LOGSPACE algorithms are naturally described as programs that operate on a structured input (e.g. a graph), that store in memory only a constant number of pointers (e.g. to graph$~$ nodes) and that do not use pointer arithmetic. Such “pure pointer algorithms” thus are a useful abstraction for studying the nature of LOGSPACE-computation. In this paper we$~$ introduce a formal class PURPLE of pure pointer programs and study them on locally ordered graphs. Existing classes of pointer algorithms, such as Jumping Automata on Graphs$~$ (JAGs) or Deterministic Transitive Closure (DTC) logic, often exclude simple programs. PURPLE subsumes these classes and allows for a natural representation of many graph$~$ algorithms that access the input graph by a constant number of pure pointers. It does so by providing a primitive for iterating an algorithm over all nodes of the input graph in an unspecified order. Since$~$ pointers are given as an abstract data type rather than as binary digits we expect that logarithmic-size worktapes cannot be encoded using pointers as is done, e.g. in totally-ordered DTC$~$ logic. We show that this is indeed the case by proving that the property “the number of nodes is a power of two,” which is in LOGSPACE, is not representable in PURPLE.

Document Actions