The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet

DOI10.1007/BF00271345zbMath0357.68073OpenAlexW2081942471MaRDI QIDQ1239007

Burkhard Monien

Publication date: 1977

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00271345

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (3)

Some results concerning two-dimensional turing machines and finite automata ⋮ Finite automata and unary languages ⋮ Hierarchies of one-way multihead automata languages

Cites Work

• Unnamed Item
• On tape-bounded complexity classes and multihead finite automata
• Transformational methods and their application to complexity problems
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Counter machines and counter languages

This page was built for publication: The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet