Journal article

Publication year: 2014

Pages: 553-569

Journal: Acta Informatica

Volume number: 51

Issue number: 8

ISSN: 0001-5903

eISSN: 1432-0525

DOI Link: https://doi.org/10.1007/s00236-014-0206-x

Publisher: Springer

Abstract: 
Unary deterministic one-way multi-head finite automata characterize the unary regular languages. Here they are studied with respect to the existence of head and state hierarchies. It turns out that for any fixed number of states, there is an infinite proper head hierarchy. In particular, the head hierarchy for stateless deterministic one-way multi-head finite automata is obtained using unary languages. On the other hand, it is shown that for a fixed number of heads, states are more powerful than states. Finally, the open question of whether emptiness is undecidable for stateless one-way two-head finite automata is addressed and, as a partial answer, undecidability can be shown if at least four states are provided.

Harvard Citation style: Kutrib, M., Malcher, A. and Wendlandt, M. (2014) Head and state hierarchies for unary multi-head finite automata, Acta Informatica, 51(8), pp. 553-569. https://doi.org/10.1007/s00236-014-0206-x

APA Citation style: Kutrib, M., Malcher, A., & Wendlandt, M. (2014). Head and state hierarchies for unary multi-head finite automata. Acta Informatica. 51(8), 553-569. https://doi.org/10.1007/s00236-014-0206-x