Remarks on multihead pushdown automata and multihead stack automata

DOI10.1016/0022-0000(83)90032-6zbMath0516.68044MaRDI QIDQ1052822

Satoru Miyano

Publication date: 1983

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(83)90032-6

zbMATH Keywords

r.e. sets; multihead automata; time and space complexity

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D15: Complexity of computation (including implicit computational complexity)

03D25: Recursively (computably) enumerable sets and degrees

Related Items

Hierarchies of one-way multihead automata languages, k\(+1\) heads are better than k for PDAs, Algebraic languages and polyominoes enumeration

Cites Work

• Unnamed Item
• Unnamed Item
• Alternating multihead finite automata
• A hardest language recognized by two-way nondeterministic pushdown automata
• A hierarchy theorem for multihead stack-counter automata
• On 3-head versus 2-head finite automata
• Transformational methods and their application to complexity problems
• Relating refined space complexity classes
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• On two-way multihead automata
• One-way multihead writing finite automata
• Non-prinicipalité du cylindre des langages à compteur
• Le cylindre des langages linéaires
• k + 1 Heads Are Better than k
• The Hardest Context-Free Language
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• On Multi-Head Finite Automata
• One-way stack automata
• Multi-tape and multi-head pushdown automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers