Journalartikel

Jahr der Veröffentlichung: 2014

Seiten: 1141-1159

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 25

Heftnummer: 8

ISSN: 0129-0541

eISSN: 1793-6373

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

Verlag: World Scientific Publishing

Abstract: 
Stateless variants of deterministic one-way multi-head finite automata with pebbles, that is, automata where the heads can drop, sense, and pick up pebbles, are studied. The relation between heads and pebbles is investigated, and a proper double hierarcliy concerning these two resources is obtained. Moreover, it is shown that a conversion of an arbitrary automaton to a stateless automaton can always be achieved at the cost of additional heads and/or pebbles. On the other hand, there are languages where one head cannot be traded for any number of additional pebbles and vice versa. Finally, the emptiness problem and related problems are shown to be undecidable even for the 'simplest' model, namely, for stateless one-way finite automata with two heads and one pebble.

Harvard-Zitierstil: Kutrib, M., Malcher, A. and Wendlandt, M. (2014) STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES, International Journal of Foundations of Computer Science, 25(8), pp. 1141-1159. https://doi.org/10.1142/S0129054114400292

APA-Zitierstil: Kutrib, M., Malcher, A., & Wendlandt, M. (2014). STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES. International Journal of Foundations of Computer Science. 25(8), 1141-1159. https://doi.org/10.1142/S0129054114400292