Remarks on multihead pushdown automata and multihead stack automata
From MaRDI portal
Publication:1052822
DOI10.1016/0022-0000(83)90032-6zbMath0516.68044OpenAlexW2028629975MaRDI QIDQ1052822
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
Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)
Related Items (4)
Algebraic languages and polyominoes enumeration ⋮ Hierarchies of one-way multihead automata languages ⋮ k\(+1\) heads are better than k for PDAs ⋮ \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata
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
This page was built for publication: Remarks on multihead pushdown automata and multihead stack automata
