|
CIAA2003 |
START ConferenceManager |
Complexity of Printing an Acyclic Automaton
Franck Guingne,
Andre Kempe,
Florent Nicart
Presented at
Eighth International Conference on Implementation and Application of
Automata (CIAA 2003),
July 16-18, 2003
Santa Barbara, CA, USA
Abstract
This article estimates the worst-case running time complexity for traversing and printing all successful paths of a normalized trim acyclic
automaton. First, we show that the worst-case structure is a garland with distribution of arcs on states as uniform as possible. Then, we prove
that the complexity is maximum when we have a distribution of e (Neper constant) outgoing arcs per state on average,and that it can be
exponential in the number of arcs.