Konferenzpaper

Jahr der Veröffentlichung: 2008

Seiten: 795-811

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 19

Heftnummer: 4

ISSN: 0129-0541

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

Konferenz: 9th International Workshop on Descriptional Complexity of Formal Systems

Verlag: World Scientific Publishing

Abstract: 
The simulation of weak restarting automata, i.e., classical restarting automata accepting exactly the regular languages, by finite automata is studied. Some of the trade-offs in the number of states when changing the representation are known. Here we continue the investigation in order to draw an almost complete picture of the descriptional power gained in the additional structural resources of weak restarting automata. In particular, for det-RR(1)-simulations of nondeterministic finite automata we obtain the same tight bounds as for simulations of R(1)-automata, though in some cases the latter class is much more efficient than the former. Moreover, the DFA-simulation of det-RR(1)-automata is considered. The shown bounds are of factorial order and are tight. The constructions are via alternating finite automata to DFAs. So, in addition, an upper bound for the AFA-simulation is obtained.

Harvard-Zitierstil: Kutrib, M. and Reimann, J. (2008) Optimal simulations of weak restarting automata, International Journal of Foundations of Computer Science, 19(4), pp. 795-811. https://doi.org/10.1142/S0129054108005966

APA-Zitierstil: Kutrib, M., & Reimann, J. (2008). Optimal simulations of weak restarting automata. International Journal of Foundations of Computer Science. 19(4), 795-811. https://doi.org/10.1142/S0129054108005966