Publication Search Form

Keywords

Authors

Year

We found publication with these paramters.

Acyclic Networks maximizing the Printing complexity

Franck Guingne, Andre Kempe, Florent Nicart
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.
To appear in the Journal TCS (Theoritical Computer Science)
2003
2003/071

Attachments

Acyclic-Networks.pdf (295.81 kB)