Journalartikel

Jahr der Veröffentlichung: 2014

Seiten: 877-896

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 25

Heftnummer: 7

ISSN: 0129-0541

eISSN: 1793-6373

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

Verlag: 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-Zitierstil: 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-Zitierstil: 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