A necessary condition for the rationality of the zeta function of a regular language

The zeta function of a formal language L is the series exp(\(\sum_{n\geq 1}a_ nx^ n/n)\), where \(a_ n\) is the number of words of length n in L. The author shows that if L is regular and if its zeta function is regular, then it has integer coefficients and each irreducible factor of its numerator and denominator divides the denominator of the generating function \(\sum_{n\geq 0}a_ nx^ n\) of L (which is rational, L being regular). He shows, under the same hypothesis, that there are cyclic languages \(L_ 1\) and \(L_ 2\) such that the generating function G(L) of L is \(G(L_ 1)-G(L_ 2)\) (a language is cyclic if (i) uv\(\in L\Leftrightarrow vu\in L\) and (ii) \(w\in L\Leftrightarrow w^ n\in L\) (n\(\geq 1))\). Moreover, it is decidable whether the zeta function of a regular language is rational.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: A necessary condition for the rationality of the zeta function of a regular language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122359)