*On the structure of the counting function of sparse context-free
languages*

Flavio D'Alessandro (Università di Roma "La Sapienza")

Joint work with Benedetto Intrigila and Stefano Varricchio

Given a language *L*, the counting function
*f*_{L} is the map which associates with any non
negative integer *n*, the number
*f*_{L}(*n*) of all the words in *L* having
length equal to *n*.
A language *L* is called sparse if its counting function is
polynomially upper bounded. Sparse languages have been widely
investigated both in Complexity and in Formal Language Theory.

In this talk, we consider sparse context-free languages. For these we give
an exact description of the counting function of a sparse context-free
language. Let *L* be a sparse context-free language and let
*f*_{L} be its counting function. Then there exist
polynomials *p*_{0}, *p*_{1}, ...,
*p*_{k-1}, with rational coefficients, and an integer
constant *k*_{0}, such that for any
*n*≥*k*_{0} one has
*f*_{L}(*n*) =
*p*_{j}(*n*) where *j* is such that *j*
≡ *n* mod *k*. As a consequence one can easily show the
decidability of some questions concerning sparse context-free languages.
Finally, we show that for any sparse context-free language *L* there
exists a regular language *L*' such that for any *n*≥0 one
has *f*_{L}(*n*) =
*f*_{L'}(*n*) and, therefore,
*f*_{L} is rational.