Journal article

Publication year: 2014

Pages: 877-896

Journal: International Journal of Foundations of Computer Science

Volume number: 25

Issue number: 7

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054114400139

Publisher: World Scientific Publishing

Abstract: 
We investigate the descriptional complexity of deterministic one-way multi-head finite automata accepting unary languages. It is known that in this case the languages accepted are regular. Thus, we study the increase of the number of states when an n-state k-head finite automaton is simulated by a classical (one-head) deterministic or nondeterministic finite automaton. In the former case upper and lower bounds that are tight in the order of magnitude are shown. For the latter case we obtain an upper bound of O(n(2k)) and a lower bound of Omega (n(k)) states. We investigate also the costs for the conversion of one-head nondeterministic finite automata to deterministic k-head finite automata, that is, we trade nondeterminism for heads. In addition, we study how the conversion costs vary in the special case of finite and, in particular, of singleton unary lanuages. Finally, as an application of the simulation results, we show that decidability problems for unary deterministic k-head finite automata such as emptiness or equivalence are LOGSPACE-complete.

Harvard Citation style: Kutrib, M., Malcher, A. and Wendlandt, M. (2014) SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA, International Journal of Foundations of Computer Science, 25(7), pp. 877-896. https://doi.org/10.1142/S0129054114400139

APA Citation style: Kutrib, M., Malcher, A., & Wendlandt, M. (2014). SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA. International Journal of Foundations of Computer Science. 25(7), 877-896. https://doi.org/10.1142/S0129054114400139