%0 Conference Proceedings
%T On the Average Complexity of Strong Star Normal Form
%+ Departamento de Ciência de Computadores (DCC)
%A Broda, Sabine
%A Machiavelo, António
%A Moreira, Nelma
%A Reis, Rogério
%Z Part 2: Contributed Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 19th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Milano, Italy
%Y Giovanni Pighizzini
%Y Cezar Câmpeanu
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10316
%P 77-88
%8 2017-07-03
%D 2017
%R 10.1007/978-3-319-60252-3_6
%Z Computer Science [cs]Conference papers
%X For regular expressions in (strong) star normal form a large set of efficient algorithms is known, from conversions into finite automata to characterisations of unambiguity. In this paper we study the average complexity of this class of expressions using analytic combinatorics. As it is not always feasible to obtain explicit expressions for the generating functions involved, here we show how to get the required information for the asymptotic estimates with an indirect use of the existence of Puiseux expansions at singularities. We study, asymptotically and on average, the alphabetic size, the size of the $\varepsilon $-follow automaton and the ratio of these expressions to standard regular expressions.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01657014/document
%2 https://inria.hal.science/hal-01657014/file/440206_1_En_6_Chapter.pdf
%L hal-01657014
%U https://inria.hal.science/hal-01657014
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10316