On the Average Complexity of Strong Star Normal Form - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

On the Average Complexity of Strong Star Normal Form

Sabine Broda
  • Fonction : Auteur
  • PersonId : 1022729
António Machiavelo
  • Fonction : Auteur
  • PersonId : 1022730
Nelma Moreira
  • Fonction : Auteur
  • PersonId : 1022731
Rogério Reis
  • Fonction : Auteur
  • PersonId : 1022732

Résumé

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.
Fichier principal
Vignette du fichier
440206_1_En_6_Chapter.pdf (438.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01657014 , version 1 (06-12-2017)

Licence

Paternité

Identifiants

Citer

Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis. On the Average Complexity of Strong Star Normal Form. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.77-88, ⟨10.1007/978-3-319-60252-3_6⟩. ⟨hal-01657014⟩
35 Consultations
118 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More