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)

Mathematics Subject Classification ID

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

Cites work

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

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)