Traversal-invariant definability and Logarithmic-space computation

EasyChair Preprint 352

Abstract

In the presence of arithmetic, order-invariant definability in first-order logic captures constant parallel time, i.e. uniform AC⁰ [I]. The ordering is necessary to replicate the presentation of a structure on the input tape of a machine. What if that ordering was in fact a traversal of the structure? We show that an analogous notion of traversal-invariant definability characterizes deterministic logarithmic space (L) and that breadth-first traversals characterize nondeterministic logarithmic space (NL). The surprising feature of these characterizations is that we can work entirely within the framework of first-order logic without any extensions, other than the traversals themselves.

Keyphrases: first-order logic, invariant definability, logarithmic space

@booklet{EasyChair:352,
  author    = {Steven Lindell and Scott Weinstein},
  title     = {Traversal-invariant definability and Logarithmic-space computation},
  doi       = {10.29007/8jb5},
  howpublished = {EasyChair Preprint 352},
  year      = {EasyChair, 2018}}