TY  - JOUR
A1  - Bubenzer, Johannes
T1  - Cycle-aware minimization of acyclic deterministic finite-state automata
JF  - Discrete applied mathematics
N2  - 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.
KW  - Minimization
KW  - Deterministic finite state automata
KW  - Algorithmic
Y1  - 2014
U6  - https://doi.org/10.1016/j.dam.2013.08.003
SN  - 0166-218X
SN  - 1872-6771
VL  - 163
SP  - 238
EP  - +
PB  - Elsevier
CY  - Amsterdam
ER  -