Publication Search Form




We found publication with these paramters.

Computing the follow automaton of an expression

Jean-Marc Champarnaud, Florent Nicart, Djelloul Ziadi
Small nondeterministic recognizers are very useful in practical applications based on regular expression searching. The follow automaton, recently introduced by Ilie and Yu, is such a small recognizer, since it is a quotient of the position automaton. The aim of this paper is to present an efficient computation of this quotient, based on specific properties of the ZPC-structure of the expression. The motivation is twofold. Since this structure is already a basic tool for computing the position automaton. Antimirov s automaton and Hromkovic s automaton, the design of an algorithm for computing the follow automaton via this structure makes it easier to compare all these small recognizers. Secondly such an algorithm provides a straightforward alternative to the rather sophisticated handling of e-transitions used in the origianl algorithm.
Ninth International Conference on Implementation and Application of Automata, Kingston, Canada, July 22-24, 2004.