| Автор | Hagenah, Christian |
| Автор | Muscholl, Anca |
| Дата выпуска | 2000 |
| dc.description | 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(n <sup>2</sup>) 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 log<sup>2</sup>(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. |
| Формат | application.pdf |
| Издатель | EDP Sciences |
| Копирайт | © EDP Sciences, 2000 |
| Тема | Epsilon-free nondeterministic automata |
| Тема | regular expressions |
| Тема | common follow sets construction. |
| Название | Computing ϵ-Free NFA from Regular Expressions in O(n log<sup>2</sup>(n)) Time |
| Тип | research-article |
| DOI | 10.1051/ita:2000116 |
| Electronic ISSN | 1290-385X |
| Print ISSN | 0988-3754 |
| Журнал | RAIRO - Theoretical Informatics and Applications |
| Том | 34 |
| Первая страница | 257 |
| Последняя страница | 277 |
| Аффилиация | Hagenah Christian; Institut für Informatik, Universität Stuttgart, Breitwiesenstr. 20-22, 70565 Stuttgart, Germany. |
| Аффилиация | Muscholl Anca; LIAFA, Université Paris VII, 2 place Jussieu, Case 7014, 75251 Paris Cedex 05, France; e-mail: muscholl@liafa.jussieu.fr; 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: muscholl@liafa.jussieu.fr |
| Выпуск | 4 |
