Open AccessRunning Time Complexity of Printing an Acyclic Automaton
Author(s) -
Franck Guingne,
André Kempe,
Florent Nicart
Publication year - 2003
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-40561-5
DOI - 10.1007/3-540-45089-0_13
Subject(s) - traverse , automaton , computer science , state (computer science) , constant (computer programming) , algorithm , time complexity , trim , finite state machine , computational complexity theory , discrete mathematics , mathematics , theoretical computer science , programming language , geodesy , geography , operating system
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 that it can be exponential in the number of arcs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom