Geodesic
Counting occurrences for a finite set of words: an inclusion-exclusion approach
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

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>i..e.</i>, 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. 
@article{DMTCS_2007_special_253_a25,
     author = {Bassino, Fr\'ed\'erique and Cl\'ement, Julien and Fayolle, J. and Nicod\`eme, P.},
     title = {Counting occurrences for a finite set of words: an inclusion-exclusion approach},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3543},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3543/}
}
TY  - JOUR
AU  - Bassino, Frédérique
AU  - Clément, Julien
AU  - Fayolle, J.
AU  - Nicodème, P.
TI  - Counting occurrences for a finite set of words: an inclusion-exclusion approach
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3543/
DO  - 10.46298/dmtcs.3543
LA  - en
ID  - DMTCS_2007_special_253_a25
ER  - 
%0 Journal Article
%A Bassino, Frédérique
%A Clément, Julien
%A Fayolle, J.
%A Nicodème, P.
%T Counting occurrences for a finite set of words: an inclusion-exclusion approach
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3543/
%R 10.46298/dmtcs.3543
%G en
%F DMTCS_2007_special_253_a25
Bassino, Frédérique; Clément, Julien; Fayolle, J.; Nicodème, P. Counting occurrences for a finite set of words: an inclusion-exclusion approach. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3543. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3543/

Cité par Sources :