Direct construction of minimal acyclic finite states automata

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.