Comments on “Incremental Construction and Maintenance of Minimal Finite-State Automata,” by Rafael C. Carrasco and Mikel L. Forcada
Jan Daciuk · Computational Linguistics · 2004
In a recent article, Carrasco and Forcada (June 2002) presented two algorithms: one for incremental addition of strings to the language of a minimal, deterministic, cyclic automaton, and one for incremental removal of strings from the automaton. The first algorithm is a generalization of the “algorithm for unsorted data”—the second of the two incremental algorithms for construction of minimal, deterministic, acyclic automata presented in Daciuk et al. (2000). We show that the other algorithm in the older article—the “algorithm for sorted data”—can be generalized in a similar way. The new algorithm is faster than the algorithm for addition of strings presented in Carrasco and Forcada's article, as it handles each state only once.