Konferenzpaper

Jahr der Veröffentlichung: 2008

Seiten: 1152-1160

Zeitschrift: Information and Computation

Bandnummer: 206

Heftnummer: 9-10

ISSN: 0890-5401

eISSN: 1090-2651

DOI Link: https://doi.org/10.1016/j.ic.2008.03.016

Konferenz: 1st International Conference on Language and Automata Theory and Applications

Verlag: Elsevier

Abstract: 
The descriptional complexity of restarting automata is investigated. We distinguish the classes of weak restarting automata, i.e., classical restarting automata accepting exactly the regular languages. In order to investigate the descriptional power gained by the additional structural resources of restarting automata, we study the trade-offs in the number of states when changing the representation to classical finite automata. The bounds shown are tight in the exact number of states. Interestingly, for a particular class we can show the tight bounds 2(n) + 1 and 2(n) for DFA and NFA conversion, respectively, by a fooling set technique. So, the power gained by the resources given to restarting automata seems to be different compared with nondeterminism. (C) 2008 Elsevier Inc. All rights reserved.

Harvard-Zitierstil: Kutrib, M. and Reimann, J. (2008) Succinct description of regular languages by weak restarting automata, Information and computation, 206(9-10), pp. 1152-1160. https://doi.org/10.1016/j.ic.2008.03.016

APA-Zitierstil: Kutrib, M., & Reimann, J. (2008). Succinct description of regular languages by weak restarting automata. Information and computation. 206(9-10), 1152-1160. https://doi.org/10.1016/j.ic.2008.03.016