Maze recognizing automata and nondeterministic tape complexity

DOI10.1016/S0022-0000(73)80031-5zbMATH Open0273.02022MaRDI QIDQ2264758FDOQ2264758

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

• Relationships between nondeterministic and deterministic tape complexities
• Title not available (Why is that?)
• Computability of Recursive Functions

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)