Direct construction of minimal acyclic finite states automata

TitleDirect construction of minimal acyclic finite states automata
Publication TypeJournal Article
Year of Publication2000
AuthorsMihov S
JournalAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Volume92
IssueLivre 2 - Mathématiques Appliquée et Informatique
Pagination87-104
ISSN0205-0808
Keywordsconstruction of minimal automaton, minimal acyclic finite states automaton
Abstract

This paper presents automaton construction algorithms based on the method for direct building of minimal acyclic finite states automaton for a given list [2]. A detailed presentation of the base algorithm with correctness and complexity proofs is given. The memory complexity of the base algorithm is $O(m)$ and the worst-case time complexity is $O(n \log(m))$, where $n$ is the total number of letters in the input list, $m$ is the size of the resulting minimal automaton. Further we present algorithms for direct construction of minimal automaton presenting the union, intersection and difference of acyclic automata. In the case of intersection and difference only the first input automaton has to be acyclic. The memory complexity of those construction algorithms is $O(m)$, and the time complexity is $O(n \log(m))$ for union and $O(n_1 + n \log(m))$ for intersection and difference, where $n_1$ is the total number of letters in the first automaton language, $n$ is the number of all letters in the resulting automaton language and $m$ is the number of states of the resulting minimal automaton. For construction of minimal automata for large scale languages, in the practice our algorithms deliver significantly better efficiency than the standard algorithms.

1991/95 MSC

68Q68, 68Q45

AttachmentSize
PDF icon 92-087-104.pdf1.62 MB