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

DOI10.1007/BF00271345MaRDI QIDQ1239007zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Counter machines and counter languages
• scientific article; zbMATH DE number 3468805 (Why is no real title available?)
• On tape-bounded complexity classes and multihead finite automata
• Transformational methods and their application to complexity problems

Cited in

(3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1239007)