zbMATH — the first resource for mathematics

Incremental construction and maintenance of minimal finite-state automata. (English) Zbl 1232.68080
Summary: J. Daciuk et al. [ibid. 26, No. 1, 3–16 (2000; Zbl 1232.68081)] describe a method for constructing incrementally minimal, deterministic, acyclic finite-state automata (dictionaries) from sets of strings. But acyclic finite-state automata have limitations: For instance, if one wants a linguistic application to accept all possible integer numbers or Internet addresses, the corresponding finite state automaton has to be cyclic. In this article, we describe a simple and equally efficient method for modifying any minimal finite-state automaton (be it acyclic or not) so that a string is added to or removed from the language it accepts; both operations are very important when dictionary maintenance is performed and solve the dictionary construction problem addressed in [loc. cit.] as a special case. The algorithms proposed here may be straightforwardly derived from the customary textbook constructions for the intersection and the complementation of finite-state automata; the algorithms exploit the special properties of the automata resulting from the intersection operation when one of the finite-state automata accepts a single string.

68Q45 Formal languages and automata
91F20 Linguistics
Full Text: DOI
[1] 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.