One-way simple multihead finite automata are not closed under concatenation

DOI10.1016/0304-3975(83)90096-8zbMath0523.68070OpenAlexW1973131466WikidataQ126340397 ScholiaQ126340397MaRDI QIDQ1056554

Juraj Hromkovič, Pavol Ďuriš

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90096-8

zbMATH Keywords

concatenationone-way simple multihead finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

Reversal-bounded nondeterministic multicounter machines and complementation ⋮ Hierarchies of one-way multihead automata languages ⋮ Tradeoffs for language recognition on alternating machines ⋮ Some classes of languages in \(NC^ 1\) ⋮ Alternating simple multihead finite automata

Cites Work

• A note on semilinear sets and bounded-reversal multihead pushdown automata
• A useful device for showing the solvability of some decision problems
• Finite automata with multiplication
• One-way simple multihead finite automata

This page was built for publication: One-way simple multihead finite automata are not closed under concatenation