Conference paper

Publication year: 2008

Pages: 795-811

Journal: International Journal of Foundations of Computer Science

Volume number: 19

Issue number: 4

ISSN: 0129-0541

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

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

Publisher: 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 Citation style: 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 Citation style: 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