Two way deterministic pushdown automaton languages and some open problems in the theory of computation
- 1 October 1974
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 170-177
- https://doi.org/10.1109/swat.1974.29
Abstract
We consider some of the important unsolved problems in the theory of computation concerning the relationship between deterministic and nondeterministic computations, and between tape and time bounded computations. For each such problem we find an equivalent problem concerning two way deterministic pushdown automaton languages. This is the first time many of the open problems have been reduced to questions about one class of automata.Keywords
This publication has 13 references indexed in Scilit:
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languagesTheory of Computing Systems, 1976
- On tape-bounded complexity classes and multi-head finite automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- On two-way multihead automataJournal of Computer and System Sciences, 1973
- An observation on time-storage trade offPublished by Association for Computing Machinery (ACM) ,1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- Two-way pushdown automataInformation and Control, 1967
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965