Conference paper

Publication year: 2008

Pages: 1152-1160

Journal: Information and Computation

Volume number: 206

Issue number: 9-10

ISSN: 0890-5401

eISSN: 1090-2651

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

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

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