# Efficient Construction of the Equation Automaton
###### Abstract  
This paper describes a fast algorithm for constructing directly the equation automaton from the well-known Thompson automaton associated with a regular expression. [PERSON] and [PERSON] have presented a unified construction of small automata and gave a construction of the equation automaton with time and space complexity in \(O(m\ \log\ m+m^{2})\), where \(m\) denotes the number of Thompson automaton transitions. It is based on two classical automata operations, namely epsilon-removal and [PERSON]'s algorithm for deterministic Finite Automata (DFA) minimization. Using the notion of c-continuation, [PERSON] et al. presented a fast computation of the equation automaton in \(O(m^{2})\) time complexity. In this paper, we design an output-sensitive algorithm combining advantages of the previous algorithms and show that its computational complexity can be reduced to \(O(m\times|Q_{m_{c}}|)\), where \(|Q_{m_{c}}|\) denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA). regular expressions; finite automata; efficient algorithms +
Footnote †: journal: _Algorithms_  
0000-0002-4000-0000-0000-0000-0000-0000-0000-0000-00000-0000-0000-0000-0000-0000-0000-00000-00000-00000-0000-00000-00000-00000-  
expressions. Their algorithms are based on two standard automata operations applied to the [PERSON] automata [11; 12] called: epsilon-remove and [PERSON]'s algorithm for DFA minimization [13]. The complexity of their construction for the equation automaton is in \(O(m\log\ m+m^{2})\), where \(m\) is the number of [PERSON] automaton transitions. Notice that, by construction the number of transitions of the [PERSON] automaton \(m\) and the size of a regular expression \(n\) are proportional. Thus, we have \(m=O(n)\). To improve the time complexity of computing the equation automaton from a regular expression E, we design an algorithm, combining advantages of previous methods [6; 7; 8], with a worst-case time complexity in \(O(m\times|Q_{\equiv_{e}}|)\), where \(|Q_{\equiv_{e}}|\) denotes the number of its states. Our approach is based on Bubenzer minimization of an acyclic DFA instead [PERSON]'s algorithm for DFA minimization step used in [PERSON]'s method. The main idea is to associate implicitly each c-continuation to a corresponding state, called _position state_ in the [PERSON] automaton by a special marking of \(\varepsilon\)-transitions. As a consequence of this marking, the right language of each position state in the Thompson automaton represents implicitly its c-continuation, called _pseudo-continuation_. After that, we disable temporarily the cyclic \(\varepsilon\)-transition in the [PERSON] automaton and perform Bubenzer minimization of an acyclic DFA to compute efficiently partial derivatives equivalence relation over the set of position states. Finally, we remove indexed \(\varepsilon\)-transitions, enable the cyclic \(\varepsilon\)-transition and then compute the \(\varepsilon\)-closure of states in the produced automaton from the previous step to get the equation automaton. The implementation of the proposed algorithm is available under the repository [[https://github.com/FaissalOuardi/Equation-automaton](https://github.com/FaissalOuardi/Equation-automaton)]([https://github.com/FaissalOuardi/Equation-automaton](https://github.com/FaissalOuardi/Equation-automaton)), (accessed on 27 May 2021). The paper is organized as follows. Section 2 contains some basic definitions and necessary preliminaries. Section 3 summarizes theoretical results that lead to c-continuations of a regular expression, and their relations with the partial derivatives. The definition of the c-continuation automaton is recalled, as well as the way it is connected to the equation automaton. Section 4 is a recall to the algorithm due to [PERSON] and [PERSON].