Head and state hierarchies for unary multi-head finite automata

DOI10.1007/s00236-014-0206-xzbMath1304.68110OpenAlexW2041114760MaRDI QIDQ478518

Andreas Malcher, Matthias Wendlandt, Martin Kutrib

Publication date: 3 December 2014

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

Full work available at URL: https://doi.org/10.1007/s00236-014-0206-x

zbMATH Keywords

deterministic one-way multi-head finite automataemptiness problemstate hierarchystateless automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

One-way reversible multi-head finite automata, Investigations on Automata and Languages Over a Unary Alphabet, Descriptional complexity of regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On stateless deterministic restarting automata
• Complexity of multi-head finite automata: origins and directions
• On stateless multihead automata: hierarchies and the emptiness problem
• Hierarchies of one-way multihead automata languages
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA
• ON STATELESS AUTOMATA AND P SYSTEMS
• On Stateless Multicounter Machines
• On Stateless Multihead Finite Automata and Multihead Pushdown Automata
• k + 1 Heads Are Better than k
• Bounded-reversal multihead finite automata languages
• Hierarchies and Characterizations of Stateless Multicounter Machines
• On Multi-Head Finite Automata
• One-way multihead finite automata and 2-bounded languages