A technology for reverse-engineering a combinatorial problem from a rational generating function

In this paper, we tackle the problem of giving, by means of a regular langu age, a combinatorial interpretation of a positive sequence (f(n)) defined b y a linear recurrence with integer coefficients. We propose two algorithms able to determine if the rational generating function of (f(n)), f(chi), is the generating function of some regular language, and, in the affirmative case, to find it. We illustrate some applications of this method to combina torial object enumeration problems and bijective combinatorics and discuss an open problem regarding languages having a rational generating function. (C) 2001 Academic Press.