Traversal-Invariant Characterizations of Logarithmic Space
Document Type
Book
Role
Contributor
Publication
The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Volume
119
First Page
2:1
Last Page
2:17
Publication Date
6-2024
Abstract
We give a novel descriptive-complexity theoretic characterization of L and NL computable queries over finite structures using traversal invariance. We summarize this as (N)L = FO + (breadth-first) traversal-invariance.
Repository Citation
Siddharth Bhaskar, Steven Lindell, and Scott Weinstein. Traversal-Invariant Characterizations of Logarithmic Space. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) https://doi.org/10.4230/OASIcs.Tannen.2
COinS
