The LBA-problem and the deterministic tape complexity of two-way one-counter languages over a one-letter alphabet
- 1 October 1977
- journal article
- Published by Springer Nature in Acta Informatica
- Vol. 8 (4) , 371-382
- https://doi.org/10.1007/bf00271345
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- Transformational methods and their application to complexity problemsActa Informatica, 1976
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languagesJournal of the ACM, 1975
- On tape-bounded complexity classes and multihead finite automataJournal of Computer and System Sciences, 1975
- Two way deterministic pushdown automaton languages and some open problems in the theory of computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- On the structure of complexity classesPublished by Springer Nature ,1974
- Rekursive Funktionen und ihre KomplexitätPublished by Springer Nature ,1974
- A note on multihead automata and context-sensitive languagesActa Informatica, 1973
- Counter machines and counter languagesTheory of Computing Systems, 1968