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