Abstract
Minimal acyclic deterministic finite automata (ADFAs) can be used as a compact representation of finite string sets with fast access time. Creating them with traditional algorithms of DFA minimization is resource greedy when a large collection of strings is involved. This paper aims to popularize an efficient but little-known algorithm for creating minimal ADFAs recognizing a finite language, invented independently by several authors. The algorithm is presented for three variants of ADFAs, its minor improvements are discussed, and minimal ADFAs are compared to competitive data structures.
| Original language | English |
|---|---|
| Pages (from-to) | 1077-1090 |
| Number of pages | 14 |
| Journal | Software - Practice and Experience |
| Volume | 31 |
| Issue number | 11 |
| DOIs | |
| Publication status | Published - Sept 2001 |
Keywords
- Acyclic finite automaton
- Direct acyclic graph
- Static dictionary
- Static lexicon
- Trie compaction
ASJC Scopus subject areas
- Software
Fingerprint
Dive into the research topics of 'How to squeeze a lexicon'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver