Stack languages and log n space

DOI10.1016/0022-0000(78)90010-7zbMath0388.68070OpenAlexW2081819676MaRDI QIDQ1250712

K. Appert

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90010-7

Mathematics Subject Classification ID

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

Related Items

Space Complexity of Stack Automata Models ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ The role of rudimentary relations in complexity theory ⋮ Space Complexity of Stack Automata Models

Cites Work

• Unnamed Item
• Unnamed Item
• On tape-bounded complexity classes and multihead finite automata
• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• Deterministic stack automata and the quotient operator
• Checking automata and one-way stack languages
• Relationships between nondeterministic and deterministic tape complexities
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• On two-way multihead automata
• Rudimentary relations and stack languages
• Stack automata and compiling
• One-way stack automata
• Nested Stack Automata
• Quasi-realtime languages
• Sets accepted by one-way stack automata are context sensitive
• Language recognition by marking automata