Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation
| dc.contributor.author | Galil, Zvi | en_US |
| dc.date.accessioned | 2007-04-19T19:07:55Z | |
| dc.date.available | 2007-04-19T19:07:55Z | |
| dc.date.issued | 1974-04 | en_US |
| dc.description.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 and phrases: Two way deterministic pushdown automata, open problems, determinism versus nondeterminism, space bounded computations, time bounded computations, Turing machines, multihead pushdown automata, two way counter machines, auxiliary pushdown machines. | en_US |
| dc.format.extent | 1779064 bytes | |
| dc.format.extent | 519790 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR74-204 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6044 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation | en_US |
| dc.type | technical report | en_US |