×

zbMATH — the first resource for mathematics

Comments on “Incremental construction and maintenance of minimal finite-state automata”. (English) Zbl 1234.68207
Summary: In a recent article, R. C. Carrasco and M. L. Forcada [ibid. 28, No. 2, 207–216 (2002; Zbl 1232.68080)] 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 [J. Daciuk et al., ibid. 26, No. 1, 3–16 (2000; Zbl 1232.68081)]. 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, loc. cit.], as it handles each state only once.

MSC:
68Q45 Formal languages and automata
91F20 Linguistics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1162/089120102760173652 · Zbl 1232.68080 · doi:10.1162/089120102760173652
[2] DOI: 10.1162/089120100561601 · Zbl 1232.68081 · doi:10.1162/089120100561601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.