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

DOI10.1016/0304-3975(83)90096-8zbMATH Open0523.68070OpenAlexW1973131466WikidataQ126340397 ScholiaQ126340397MaRDI QIDQ1056554FDOQ1056554

Authors: Pavol Ďuriš, Juraj Hromkovič 

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)

Cites Work

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

Cited In (5)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1056554)