In a previous work, Hofmann and Schöpp have introduced the programming language
to formalise the common intuition of
-algorithms as pure pointer programs that take as input some structured data (e.g. a graph) and store in memory only a constant number of pointers to the input (e.g. to the graph nodes). It was shown that
is strictly contained in
, being unable to decide
-connectivity in undirected graphs.
In this paper we study the options of strengthening
as a manageable idealisation of computation with logarithmic space that may be used to give some evidence that
-problems such as Horn satisfiability cannot be solved in logarithmic space.
We show that with counting,
captures all of
on locally ordered graphs. Our main result is that without a local ordering, even with counting and nondeterminism,
cannot solve tree isomorphism. This generalises the same result for Transitive Closure Logic with counting, to a formalism that can iterate over the input structure, furnishing a new proof as a by-product.