Hierarchies of one-way multihead automata languages
From MaRDI portal
Publication:1099645
DOI10.1016/0304-3975(86)90093-9zbMath0638.68097MaRDI QIDQ1099645
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90093-9
68Q45: Formal languages and automata
Related Items
One-way multihead finite automata and 2-bounded languages, k\(+1\) heads are better than k for PDAs, Tradeoffs for language recognition on alternating machines, Multihead one-way finite automata
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Remarks on multihead pushdown automata and multihead stack automata
- One-way simple multihead finite automata are not closed under concatenation
- Variations on the technique of Ďuriš and Galil
- A hierarchy theorem for multihead stack-counter automata
- Fooling a two way automaton or one pushdown store is better than one counter for two way machines
- On 3-head versus 2-head finite automata
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- Space bounds for processing contentless inputs
- A useful device for showing the solvability of some decision problems
- On tape bounds for single letter alphabet language processing
- Techniques for separating space complexity classes
- Relating refined space complexity classes
- The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet
- Transformational methods and their application to complexity problems. Corrigenda
- One-way simple multihead finite automata
- One way multihead deterministic finite automata
- Multitape one-way nonwriting automata
- On non-determinacy in simple computing devices
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- On two-way multihead automata
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- One-way multihead writing finite automata
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- k + 1 Heads Are Better than k
- Bounded Algol-Like Languages
- Bounded Regular Sets
- Two-way pushdown automata
- On Multi-Head Finite Automata
- Multi-tape and multi-head pushdown automata
- An Infinite Hierarchy of Context-Free Languages
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- One-tape, off-line Turing machine computations
