n South African Computer Journal - A taxonomy of algorithms for constructing minimal acyclic deterministic finite automata
|Article Title||A taxonomy of algorithms for constructing minimal acyclic deterministic finite automata|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Publication Date||Aug 2001|
|Pages||12 - 17|
|Keyword(s)||Acyclic deterministic automata, Algorithmics, D.1.4, Dictionaries, E.1, F.2.2, G.2.2 and Minimal automata|
In this paper, we present a taxonomy of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs). Such automata represent finite languages and are therefore useful in applications such as storing words for spell-checking, computer and biological virus searching, text indexing and XML tag lookup. In such applications, the automata can grow extremely large (with more than 10 6 states) and are difficult to store without compression or minimization. The taxonomization method arrives at all of the known algorithms, and some which are likely new ones (though proper attribution is not always possible, since the algorithms are usually of commercial value and some secrecy frequently surrounds the identities of the original authors).
Article metrics loading...