On the Average Complexity of Strong Star Normal Form

Abstract : 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.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.77-88, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657014
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:37
Dernière modification le : mercredi 6 décembre 2017 - 14:04:28

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis. On the Average Complexity of Strong Star Normal Form. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.77-88, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_6〉. 〈hal-01657014〉

Partager

Métriques

Consultations de la notice

24