Maze recognizing automata and nondeterministic tape complexity

DOI10.1016/S0022-0000(73)80031-5MaRDI QIDQ2264758zbMATH OpenFDO

Authors Walter Savitch

Publication date 1973

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(73)80031-5

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• Computability of Recursive Functions
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Relationships between nondeterministic and deterministic tape complexities

Cited in

(11)

• 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
• An observation on time-storage trade off
• A space lower bound for \(st\)-connectivity on node-named JAGs
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• Balancing bounded treewidth circuits
• Complexity of testing reachability in matroids
• Path-disruption games: bribery and a probabilistic model
• Methods for proving completeness via logical reductions
• The complexity of membership problems for circuits over sets of integers

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)