Maze recognizing automata and nondeterministic tape complexity
From MaRDI portal
Publication:2264758
DOI10.1016/S0022-0000(73)80031-5zbMath0273.02022MaRDI QIDQ2264758
Publication date: 1973
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)
Related Items (11)
The complexity of membership problems for circuits over sets of integers ⋮ Balancing bounded treewidth circuits ⋮ Number of quantifiers is better than number of tape cells ⋮ Upper and lower bounds for first order expressibility ⋮ The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems ⋮ Methods for proving completeness via logical reductions ⋮ Path-disruption games: bribery and a probabilistic model ⋮ An observation on time-storage trade off ⋮ Unnamed Item ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets
Cites Work
This page was built for publication: Maze recognizing automata and nondeterministic tape complexity
