On the LBA problem
- 1 January 1981
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 265-280
- https://doi.org/10.1007/3-540-10854-8_30
Abstract
No abstract availableKeywords
This publication has 41 references indexed in Scilit:
- Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version)Published by Association for Computing Machinery (ACM) ,1981
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Simple Representations of Certain Classes of LanguagesJournal of the ACM, 1978
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languagesTheory of Computing Systems, 1976
- Translational lemmas, polynomial time, and (log n)j-spaceTheoretical Computer Science, 1976
- On Languages Accepted in Polynomial TimeSIAM 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
- Path systems and language recognitionPublished by Association for Computing Machinery (ACM) ,1970
- Time and tape complexity of pushdown automaton languagesInformation and Control, 1968