--- title: "Incremental construction of minimal acyclic finite state automata" description: "Deterministic acyclic finite-state automata, called \"dictionaries\" here, store word lists compactly and… 10 references, cited by 13 papers here." authors: ["Jan Daciuk", "Stoyan Mihov", "Bruce W. Watson", "Richard E. Watson"] year: 2000 venue: "Computational Linguistics" source: "https://aclanthology.org/J00-1002/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/daciuk-2000-incremental-construction-minimal-acyclic-finite/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/daciuk-2000-incremental-construction-minimal-acyclic-finite/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2000](https://md.research.elamur.ai/free/en/papers/2000/) / Incremental construction of minimal acyclic finite state automata # Incremental construction of minimal acyclic finite state automata **Authors:** Jan Daciuk, Stoyan Mihov, Bruce W. Watson and Richard E. Watson · **Year:** 2000 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 2000](https://md.research.elamur.ai/free/en/venues/cl/2000/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/) **Links:** [Publisher's page](https://aclanthology.org/J00-1002/) · [PDF](https://aclanthology.org/J00-1002.pdf) · [OpenAlex](https://openalex.org/W2154478838) **Citations:** 182 citations (OpenAlex, 2026-10-14) · [13](https://md.research.elamur.ai/free/en/papers/daciuk-2000-incremental-construction-minimal-acyclic-finite/cited-by/) in our library, of the 149,439 papers whose bibliographies we read ## 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 Technology](https://md.research.elamur.ai/free/en/universities/gdansk-university-of-technology/) — University, Gdansk, Poland · 4 works · 253 citations - [University of Pretoria](https://md.research.elamur.ai/free/en/universities/university-of-pretoria/) — University, Pretoria, South Africa · 9 works · 755 citations - [Bulgarian Academy of Sciences](https://md.research.elamur.ai/free/en/government/bulgarian-academy-of-sciences/) — Government body, Sofia, Bulgaria · 7 works · 554 citations 📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-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. ```bibtex @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} } ``` - [← previous Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar](https://md.research.elamur.ai/free/en/papers/chiang-2000-statistical-parsing-automatically-extracted-tree/) - [next → Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation, and user studies](https://md.research.elamur.ai/free/en/papers/radev-2000-centroid-based-summarization-multiple-documents/) - [↑ back to papers of 2000](https://md.research.elamur.ai/free/en/papers/2000/) ## 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](https://scholar.google.com/scholar?q=Daciuk%2C+Jan%2C+Bruce+W%2E+Watson%2C+and+Richard+E%2E+Watson%2E+1998%2E+Incremental+construction+of+minimal+acyclic+finite+state+automata+and+transducers%2E+In+Proceedings+of+the+International+Workshop+on+Finite+Sta) 2. Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. [find](https://scholar.google.com/scholar?q=Hopcroft%2C+John+E%2E+and+Jeffrey+D%2E+Ullman%2E+1979%2E+Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation%2E+Addison%2DWesley%2C+Reading%2C+MA%2E) 3. Mihov, Stoyan. 1998. Direct building of minimal automaton for given list. In Annuaire de l'Universitd de Sofia "St. KI. [find](https://scholar.google.com/scholar?q=Mihov%2C+Stoyan%2E+1998%2E+Direct+building+of+minimal+automaton+for+given+list%2E+In+Annuaire+de+l%27Universitd+de+Sofia+%22St%2E+KI%2E) 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](http://lml.bas.bg/,-~stoyan/publications.html). [↗](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](https://scholar.google.com/scholar?q=Moll%2C+Robert+N%2E%2C+Michael+A%2E+Arbib%2C+and+A%2E+J%2E+Kfoury%2E+1988%2E+Introduction+to+Formal+Language+Theory%2E+Springer+Verlag%2C+New+York%2C+NY%2E) 6. Revuz, Dominique. 1991. Dictionnaires et lexiques: mdthodes et algorithmes. Ph.D. thesis, Institut Blaise Pascal, Paris, France. LITP 91.44. [find](https://scholar.google.com/scholar?q=Revuz%2C+Dominique%2E+1991%2E+Dictionnaires+et+lexiques%3A+mdthodes+et+algorithmes%2E+Ph%2ED%2E+thesis%2C+Institut+Blaise+Pascal%2C+Paris%2C+France%2E+LITP+91%2E44%2E) 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](https://scholar.google.com/scholar?q=Watson%2C+Bruce+W%2E+1993a%2E+A+taxonomy+of+finite+automata+construction+algorithms%2E+Computing+Science+Note+93%2F43%2C+Eindhoven+University+of+Technology%2C+The+Netherlands%2E+Available+at+www%2EOpenFIRE%2Eorg%2E) 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](https://scholar.google.com/scholar?q=Watson%2C+Bruce+W%2E+1993b%2E+A+taxonomy+of+finite+automata+minimization+algorithms%2E+Computing+Science+Note+93%2F44%2C+Eindhoven+University+of+Technology%2C+The+Netherlands%2E+Available+at+www%2EOpenFIRE%2Eorg%2E) 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](https://scholar.google.com/scholar?q=Watson%2C+Bruce+W%2E+1995%2E+Taxonomies+and+Toolkits+of+Regular+Language+Algorithms%2E+Ph%2ED%2E+thesis%2C+Eindhoven+University+of+Technology%2C+the+Netherlands%2E+Available+at+www%2EOpenFIRE%2Eorg%2E) 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](https://scholar.google.com/scholar?q=Watson%2C+Bruce+W%2E+1998%2E+A+fast+new+semi%2Dincremental+algorithm+for+construction+of+minimal+acyclic+DFAs%2E+In+Proceedings+of+the+Third+International+Workshop+on+Implementing+Automata%2C+pages+121%2D32%2C+Rouen%2C) *Updated 30 October 2026*