Download PDFOpen PDF in browser

Traversal-invariant definability and Logarithmic-space computation

EasyChair Preprint no. 352

4 pagesDate: July 16, 2018


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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Steven Lindell and Scott Weinstein},
  title = {Traversal-invariant definability and Logarithmic-space computation},
  howpublished = {EasyChair Preprint no. 352},
  doi = {10.29007/8jb5},
  year = {EasyChair, 2018}}
Download PDFOpen PDF in browser