Portal de Periódicos da CAPES

Fast equation automaton computation

2008; Elsevier BV; Volume: 6; Issue: 3 Linguagem: Inglês

10.1016/j.jda.2007.10.003

1570-8675

Ahmed Khorsi, Faïssal Ouardi, Djelloul Ziadi,

Logic, programming, and type systems

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