On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection

Abstract : Extended regular expressions (with complement and intersection) are used in many applications due to their succinctness. In particular, regular expressions extended with intersection only (also called semi-extended) can already be exponentially smaller than standard regular expressions or equivalent nondeterministic finite automata (NFA). For practical purposes it is important to study the average behaviour of conversions between these models. In this paper, we focus on the conversion of regular expressions with intersection to nondeterministic finite automata, using partial derivatives and the notion of support. First, we give a tight upper bound of $$2^{O(n)}$$ for the worst-case number of states of the resulting partial derivative automaton, where n is the size of the expression. Using the framework of analytic combinatorics, we then establish an upper bound of $$(1.056 +o(1))^n$$ for its asymptotic average-state complexity, which is significantly smaller than the one for the worst case.
Type de document :
Communication dans un congrès
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.45-59, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_4〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01633952
Contributeur : Hal Ifip <>
Soumis le : lundi 13 novembre 2017 - 15:32:43
Dernière modification le : lundi 13 novembre 2017 - 15:35:34
Document(s) archivé(s) le : mercredi 14 février 2018 - 15:19:49

Fichier

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

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis. On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.45-59, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_4〉. 〈hal-01633952〉

Partager

Métriques

Consultations de la notice

46