Conference paper

Publication year: 2009

Pages: 3209-3222

Journal: Theoretical Computer Science

Volume number: 410

Issue number: 35

ISSN: 0304-3975

eISSN: 1879-2294

Open access status: Bronze

DOI Link: https://doi.org/10.1016/j.tcs.2009.05.019

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

Publisher: Elsevier

Abstract: 
We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, Suffix-, and infix-free languages. Most of the bounds for the conversion problem are shown to be tight ill the exact number of states, that is, the number is sufficient and necessary in the worst case. Otherwise tight bounds in order of magnitude are shown. (C) 2009 Elsevier B.V. All rights reserved.

Harvard Citation style: Bordihn, H., Holzer, M. and Kutrib, M. (2009) Determination of finite automata accepting subregular languages, Theoretical Computer Science, 410(35), pp. 3209-3222. https://doi.org/10.1016/j.tcs.2009.05.019

APA Citation style: Bordihn, H., Holzer, M., & Kutrib, M. (2009). Determination of finite automata accepting subregular languages. Theoretical Computer Science. 410(35), 3209-3222. https://doi.org/10.1016/j.tcs.2009.05.019