Elamur Research⌕
☰
home / papers / 2000 / Incremental construction of minimal acyclic finite state automata

Incremental construction of minimal acyclic finite state automata

Paper · 2000 · Jan Daciuk, Stoyan Mihov, Bruce W. Watson et al.

Summary

Deterministic acyclic finite-state automata, called "dictionaries" here, store word lists compactly and allow lookups in time proportional to word length. They are used in NLP tools such as spell-checkers and morphological analyzers. The standard way to get the smallest such automaton is to build a trie and then minimize it. However, the intermediate trie can exceed physical memory. Daciuk, Mihov, Watson and Watson remove that stage: words are inserted one by one, and the automaton stays minimal after each insertion.

States are classified by their right language. A register of pairwise inequivalent states lets each processed state either merge with an existing equivalent or become a new class. Equivalence is tested locally, using finality, transition labels and target states. The authors give two variants:

  • Sorted input: for lexicographically ordered words, only the path of the previously added word can change.
  • Arbitrary order: a general version that is slower, because changes can propagate back to the start state.

The approach greatly reduces memory use and build time for large lexicons.

Key points

  • Per word, the main loop runs once and the inner loops at most |w| steps. Register operations cost O(log n), or constant time with hashing.
  • In the sorted variant, finished parts of the automaton never change again, so other processes can use them while construction continues.
  • Daciuk's C++ implementation is free for research at www.pg.gda.pl/~jandac/fsa.html. Mihov's Java package underlies the Grammatical Web Server for Bulgarian.
  • Compared with Revuz's (1991) pseudominimization, which can leave automata about 8 times larger than minimal on DELAF, the new method needs no separate minimization phase. The same holds against Watson's (1998) semi-incremental method.
  • The method extends to transducers and has been applied to diacritic restoration, perfect hashing, document indexing, DNA matching and virus detection.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Gdańsk University of TechnologyGdansk · Poland4 works · 253 citations🎓University of PretoriaPretoria · South Africa9 works · 755 citations🏛️Bulgarian Academy of SciencesSofia · Bulgaria7 works · 554 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputational Theory and Mathematics · 321 works

Cite

Cite as Jan Daciuk, Stoyan Mihov, Bruce W. Watson and Richard E. Watson. 2000. Incremental construction of minimal acyclic finite state automata. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{daciuk2000incremental,
  title = {{Incremental construction of minimal acyclic finite state automata}},
  author = {Jan Daciuk, Stoyan Mihov, Bruce W. Watson and Richard E. Watson},
  journal = {Computational Linguistics},
  year = {2000},
  doi = {10.1162/089120100561601},
  url = {https://doi.org/10.1162/089120100561601}
}

References

10 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Daciuk, Jan, Bruce W. Watson, and Richard E. Watson. 1998. Incremental construction of minimal acyclic finite state automata and transducers. In Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, pages 48-56, Ankara, Turkey, 30 June-1 July. find
  2. Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. find
  3. Mihov, Stoyan. 1998. Direct building of minimal automaton for given list. In Annuaire de l'Universitd de Sofia "St. KI. find
  4. Ohridski', volume 91, book 1, pages 38-40. Facult4 de Mathematique et Informatique, Sofia, Bulgaria, livre 1 edition, February. Available at http://lml.bas.bg/,-~stoyan/publications.html. ↗
  5. Moll, Robert N., Michael A. Arbib, and A. J. Kfoury. 1988. Introduction to Formal Language Theory. Springer Verlag, New York, NY. find
  6. Revuz, Dominique. 1991. Dictionnaires et lexiques: mdthodes et algorithmes. Ph.D. thesis, Institut Blaise Pascal, Paris, France. LITP 91.44. find
  7. Watson, Bruce W. 1993a. A taxonomy of finite automata construction algorithms. Computing Science Note 93/43, Eindhoven University of Technology, The Netherlands. Available at www.OpenFIRE.org. find
  8. Watson, Bruce W. 1993b. A taxonomy of finite automata minimization algorithms. Computing Science Note 93/44, Eindhoven University of Technology, The Netherlands. Available at www.OpenFIRE.org. find
  9. Watson, Bruce W. 1995. Taxonomies and Toolkits of Regular Language Algorithms. Ph.D. thesis, Eindhoven University of Technology, the Netherlands. Available at www.OpenFIRE.org. find
  10. Watson, Bruce W. 1998. A fast new semi-incremental algorithm for construction of minimal acyclic DFAs. In Proceedings of the Third International Workshop on Implementing Automata, pages 121-32, Rouen, France, 17-19 September. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/daciuk-2000-incremental-construction-minimal-acyclic-finite/