Traversal-invariant characterizations of logarithmic space

Siddharth Bhaskar, Steven Lindell, Scott Weinstein

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 +…