Comments on 'Incremental Construction and Maintenance of Minimal Finite-State Automata,' by Rafael C. Carrasco and Mikel L. Forcada

摘要

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 shoxv that the other algorithm in the older article-the "algorithm for sorted data"-can be generalized in a similar ivay. 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.