Average Analysis of Glushkov Automata under a BST-Like Model

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00620382
Contributor : Cyril Nicaud <>
Submitted on : Wednesday, January 30, 2013 - 5:09:11 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:02 PM
Long-term archiving on : Monday, June 17, 2013 - 2:47:57 PM

File

nipira10.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-00620382, version 1

Citation

Cyril Nicaud, Carine Pivoteau, Benoît Razet. Average Analysis of Glushkov Automata under a BST-Like Model. 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS'10), 2010, India. pp.388-399. ⟨hal-00620382⟩

Share

Metrics

Record views

175

Files downloads

181