Maze recognizing automata and nondeterministic tape complexity
From MaRDI portal
Cites work
Cited in
(11)- Upper and lower bounds for first order expressibility
- Number of quantifiers is better than number of tape cells
- Methods for proving completeness via logical reductions
- An observation on time-storage trade off
- The complexity of membership problems for circuits over sets of integers
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Balancing bounded treewidth circuits
- Complexity of testing reachability in matroids
- A space lower bound for \(st\)-connectivity on node-named JAGs
- Resolution of Hartmanis' conjecture for NL-hard sparse sets
- Path-disruption games: bribery and a probabilistic model
This page was built for publication: Maze recognizing automata and nondeterministic tape complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2264758)