Incremental construction of minimal acyclic finite-state automata
<|reference_start|>Incremental construction of minimal acyclic finite-state automata: In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-state automata from a set of strings. Traditional methods consist of two phases: the first to construct a trie, the second one to minimize it. Our approach is to construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical ordering of the input strings.<|reference_end|>
@article{daciuk2000incremental,
    title={Incremental construction of minimal acyclic finite-state automata},
    author={Jan Daciuk, Stoyan Mihov, Bruce Watson, Richard Watson},
    journal={Computational Linguistics, Vol. 26, Number 1, March 2000},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0007009},
    primaryClass={cs.CL}
}