Enumerative combinatorics on words

Dominique Perrin (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We present the state of the art in the field of generating series for formal languages. The emphasis is on regular languages and rational series. The paper covers aspects including regular trees and the Kraft-McMillan inequality as well as necklaces and zeta functions.

Domaines: Algorithme et structure de données [cs.DS]

Dominique Perrin. Enumerative combinatorics on words. Crapo Henri, Rota Gian-Carlo. Algebraic Combinatorics and Computer Science, Springer-Verlag, pp.391-430, 2001. ⟨hal-00620805⟩