Jean-Marc Champarnaud, Florent Nicart, Djelloul Ziadi
Ninth International Conference on Implementation and Application of Automata, Kingston, Canada,
July 22-24, 2004.
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.
Report number: