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

DOI10.1016/0304-3975(83)90096-8MaRDI QIDQ1056554zbMATH OpenOpenAlexWikidataFDO

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
• Finite automata with multiplication
• One-way simple multihead finite automata

Cited in

(5)

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

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)