Fast equation automaton computation

AbstractThe most efficient known construction of equation automaton is that due to Ziadi and Champarnaud. For a regular expression E, it requires O(|E|2) time and space and is based on going from position automaton to equation automaton using c-continuations. This complexity is due to the sorting step that takes O(|E|2) time used to identify the identical sub-expressions of E. In this paper, we present a more efficient construction of the equation automaton which avoids the sorting step and replaces it by a minimization of an acyclic finite deterministic automaton. We show that this minimization allows the identification of identical sub-expressions as well as the sorting step used in Champarnaud and Ziadi's approach. Using the minimization we get O(|E|+|E|⋅|EE|) time and space complexity where |EE| is the number of states of the equation automaton