Determination of finite automata accepting subregular languages
- 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.
| Verfasserangaben: | Henning BordihnORCiD, Markus HolzerGND, Martin Kutrib |
|---|---|
| URL: | http://www.sciencedirect.com/science/journal/03043975 |
| DOI: | https://doi.org/10.1016/j.tcs.2009.05.019 |
| ISSN: | 0304-3975 |
| Publikationstyp: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Jahr der Erstveröffentlichung: | 2009 |
| Erscheinungsjahr: | 2009 |
| Datum der Freischaltung: | 25.03.2017 |
| Quelle: | Theoretical computer science. - ISSN 0304-3975. - 410 (2009), 35, S. 3209 - 3222 |
| Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| Peer Review: | Referiert |
| Name der Einrichtung zum Zeitpunkt der Publikation: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik |
