Average Analysis of Glushkov Automata under a BST-Like Model
| Autor: | Nicaud, Cyril, Pivoteau, Carine, Razet, Benoît |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Nicaud, Cyril |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
000 Computer science
knowledge general works 010201 computation theory & mathematics [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Computer Science 0202 electrical engineering electronic engineering information engineering [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] 020201 artificial intelligence & image processing 0102 computer and information sciences 02 engineering and technology 01 natural sciences |
| Zdroj: | 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS'10) 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS'10), 2010, India. pp.388-399 |
| DOI: | 10.4230/lipics.fsttcs.2010.388 |
| Popis: | International audience; We study the average number of transitions in Glushkov automata built from random regular expressions. This statistic highly depends on the probabilistic distribution set on the expressions. A recent work shows that, under the uniform distribution, regular expressions lead to automata with a linear number of transitions. However, uniform regular expressions are not necessarily a satisfying model. Therefore, we rather focus on an other model, inspired from random binary search trees (BST), which is widely used, in particular for testing. We establish that, in this case, the average number of transitions becomes quadratic according to the size of the regular expression. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|