Counting occurrences for a finite set of words: an inclusion-exclusion approach

Frédérique Bassino 1 Julien Clément 2 J. Fayolle 3 P. Nicodème 4
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
3 LRI - Laboratoire de Recherche en Informatique
4 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : In this paper, we give the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to Goulden and Jackson (1979, 1983) is used to derive the result. Unlike some other techniques which suppose that the set of words is reduced (i..e., where no two words are factor of one another), the finite set can be chosen arbitrarily. Noonan and Zeilberger (1999) already provided a MAPLE package treating the non-reduced case, without giving an expression of the generating function or a detailed proof. We give a complete proof validating the use of the inclusion-exclusion principle and compare the complexity of the method proposed here with the one using automata for solving the problem.
Keywords : word statistics inclusion-exclusion generating functions
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.31-46, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00452702
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:59:57
Dernière modification le : mardi 5 juin 2018 - 10:14:41
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:17:44

Fichier

dmAH0103.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00452702, version 2

Collections

GREYC | X | LIX | INSMI | X-LIX | UMR8623 | PARISTECH | ENPC | LIGM_MOA | TDS-MACS | UPEC-UPEM | INRIA | GREYC-AMACC | COMUE-NORMANDIE | ENSICAEN | X-DEP-INFO

Citation

Frédérique Bassino, Julien Clément, J. Fayolle, P. Nicodème. Counting occurrences for a finite set of words: an inclusion-exclusion approach. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.31-46, 2007, DMTCS Proceedings. 〈hal-00452702v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

700

Téléchargements de fichiers

293

Contact


archive-ouverte@inria.fr