Publications
Authors:
  • Franck Guingne , Andre Kempe , Florent Nicart
Citation:
To appear in the Journal TCS (Theoritical Computer Science)
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 festoon 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 (Napier constant) outgoing arcs per state on average, and it can be exponential in
the number of arcs.
Year:
2003
Report number:
2003/071
Attachments: