Filtern
Volltext vorhanden
- nein (1) (entfernen)
Erscheinungsjahr
- 2014 (1) (entfernen)
Dokumenttyp
Sprache
- Englisch (1)
Gehört zur Bibliographie
- ja (1)
Schlagworte
- Algorithmic (1) (entfernen)
Institut
- Institut für Mathematik (1) (entfernen)
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.