کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431118 | 688278 | 2008 | 16 صفحه PDF | دانلود رایگان |
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)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)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|)O(|E|+|E|⋅|EE|) time and space complexity where |EE||EE| is the number of states of the equation automaton.
Journal: Journal of Discrete Algorithms - Volume 6, Issue 3, September 2008, Pages 433–448