On 3-head versus 2-head finite automata

DOI10.1007/BF00288748zbMath0291.94029OpenAlexW2022392369MaRDI QIDQ1211473

Oscar H. Ibarra, Chul Eung Kim

Publication date: 1975

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00288748

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

Hierarchies of one-way multihead automata languages ⋮ k\(+1\) heads are better than k for PDAs ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Tradeoffs for language recognition on alternating machines ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Remarks on sorting and one-way multihead finite automata ⋮ Multihead one-way finite automata ⋮ Stack versus sensitivity for one-way automata ⋮ Binding-blocking automata ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ One-way simple multihead finite automata ⋮ Remarks on multihead pushdown automata and multihead stack automata

Cites Work

• On Multi-Head Finite Automata
• Multi-tape and multi-head pushdown automata
• Unnamed Item

This page was built for publication: On 3-head versus 2-head finite automata