On the structure of the counting function of sparse context-free
Flavio D'Alessandro (Università di Roma "La Sapienza")
Joint work with Benedetto Intrigila and Stefano Varricchio
Given a language L, the counting function fL is the map which associates with any non negative integer n, the number fL(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 fL be its counting function. Then there exist polynomials p0, p1, ..., pk-1, with rational coefficients, and an integer constant k0, such that for any n≥k0 one has fL(n) = pj(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 fL(n) = fL'(n) and, therefore, fL is rational.