activity
20182021
most citedCons-free Programs and Complexity Classes between LOGSPACE and PTIME

1 citations · 1 across the 1 of their papers we have counts for

collaborators
Showing cs.LOShow all

1 paper · 1 filter

cs.LO2020

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