Martin Hofmann (LMU, Munich, Germany), Pure pointer programs (implicit computational complexity) with an abstract datatype of pointers
Schedule
- Jan. 31, 2012, 9:00 - 10:30: part 1
- Feb. 1, 2012, 9:00 - 10:30: part 2
Abstract
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.
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.