Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00452702
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:59:57 PM
Last modification on : Saturday, May 1, 2021 - 3:39:33 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:17:44 PM

File

dmAH0103.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00452702, version 2

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. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.31-46. ⟨hal-00452702v2⟩

Share

Metrics

Record views

1165

Files downloads

991