Cycle-aware minimization of acyclic deterministic finite-state automata
- In this paper a linear-time algorithm for the minimization of acyclic deterministic finite-state automata is presented. The algorithm runs significantly faster than previous algorithms for the same task. This is shown by a comparison of the running times of both algorithms. Additionally, a variation of the new algorithm is presented which handles cyclic automata as input. The new cycle-aware algorithm minimizes acyclic automata in the desired way. In case of cyclic input, the algorithm minimizes all acyclic suffixes of the input automaton.
| Verfasserangaben: | Johannes Bubenzer |
|---|---|
| DOI: | https://doi.org/10.1016/j.dam.2013.08.003 |
| ISSN: | 0166-218X |
| ISSN: | 1872-6771 |
| Titel des übergeordneten Werks (Englisch): | Discrete applied mathematics |
| Verlag: | Elsevier |
| Verlagsort: | Amsterdam |
| Publikationstyp: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Jahr der Erstveröffentlichung: | 2014 |
| Erscheinungsjahr: | 2014 |
| Datum der Freischaltung: | 27.03.2017 |
| Freies Schlagwort / Tag: | Algorithmic; Deterministic finite state automata; Minimization |
| Band: | 163 |
| Seitenanzahl: | 9 |
| Erste Seite: | 238 |
| Letzte Seite: | + |
| Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Mathematik |
| Peer Review: | Referiert |
