2026-07-20T06:35:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2880 2024-03-06T10:33:40Z ddc:004 open_access

Average Analysis of Glushkov Automata under a BST-Like Model Nicaud, Cyril Pivoteau, Carine Razet, Benoît Glushkov automata random binary search tree regular expression 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cyril Nicaud and Carine Pivoteau and Benoît Razet 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.388 urn:nbn:de:0030-drops-28809 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.388 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode