RAIRO-Theor. Inf. Appl.
Volume 34, Number 4, July/August 2000
|Page(s)||257 - 277|
|Published online||15 April 2002|
Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time
Institut für Informatik,
Breitwiesenstr. 20-22, 70565 Stuttgart, Germany.
2 LIAFA, Université Paris VII, 2 place Jussieu, Case 7014, 75251 Paris Cedex 05, France; e-mail: firstname.lastname@example.org
3 Institut für Informatik, Universität Stuttgart, Breitwiesenstr. 20-22, 70565 Stuttgart, Germany. LIAFA, Université Paris VII, 2 place Jussieu, Case 7014, 75251 Paris Cedex 05, France; e-mail: email@example.com
Accepted: 7 August 2000
The standard procedure to transform a regular expression of size n to an ϵ-free nondeterministic finite automaton yields automata with O(n) states and O(n2) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an ϵ-free NFA with only O(n log2(n)) transitions. The current lower bound on the number of transitions is Ω(n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed by Hromkovič et al. yields a cubic algorithm. In this paper we present a sequential algorithm for the CFS construction which works in time O(n log(n) + size of the output). On a CREW PRAM the CFS construction can be performed in time O(log(n)) using O(n + (size of the output)/log(n)) processors. We also present a simpler proof of the lower bound on the number of transitions.
Mathematics Subject Classification: 68Q45 / 68Q25 / 68W01 / 68W10
Key words: Epsilon-free nondeterministic automata / regular expressions / common follow sets construction.
© EDP Sciences, 2000
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.