Martin Hofmann (LMU, Munich, Germany), Pure pointer programs (implicit computational complexity) with an abstract datatype of pointers


  • Jan. 31, 2012, 9:00 - 10:30: part 1
  • Feb. 1, 2012, 9:00 - 10:30: part 2


Pointer programs are a model of structured computation within LOGSPACE (logarithmic space on a Turing machine). 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.

We define a formalised language for pointer programs (Purple) and show that some LOGSPACE algorithms can be programmed in Purple while others cannot (e.g. reachability in undirected graphs). This yields a better understanding of the structure of LOGSPACE and also sheds new light on finite model theory; indeed, since formulas in deterministic transitive closure logic (DTC) can be evaluated in Purple it can be deduced that reachability in undirected graphs cannot be defined by a DTC formula which was hitherto unknown.

This also, somewhat trivially, separates Purple from PTIME. In order to get a more meaningful such separation we would like to strengthen Purple while still remaining strictly below PTIME. Possible such extensions are nondeterminism, iterators in the style of Java, and various patterns of recursion patterns.

The course will give an overview of Purple and related systems and results, in particular Graph Automata and DTC logic and present some of the extensions to Purple that we currently investigate.

This is joint work with Ulrich Schoepp and Ramyaa Ramyaa.