Abstract
The 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
|
⋅
|
E
E
|
)
time and space complexity where
|
E
E
|
is the number of states of the equation automaton.