EuDML | Browse

Skip to main content (access key 's'), Skip to navigation (access key 'n'), Accessibility information (access key '0')

The search session has expired. Please query the service again.

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 2 of 2

Computing $ε$ -free NFA from regular expressions in $O (n {log}^{2} (n))$ time

Christian Hagenah, Anca Muscholl (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time

Christian Hagenah, Anca Muscholl (2010)

RAIRO - Theoretical Informatics and Applications

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...

Currently displaying 1 – 2 of 2

Page 1

Displaying 1 – 2 of 2

Computing ε -free NFA from regular expressions in O ( n log 2 ( n ) ) time

Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time

Currently displaying 1 – 2 of 2

Computing $ε$ -free NFA from regular expressions in $O (n {log}^{2} (n))$ time