On generalized zeta functions of formal languages and series (Q1179183)

The zeta functions and generalized zeta functions of formal languages and power series were introduced by \textit{J. Berstel} and \textit{C. Reutenauer} [Lect. Notes Comput. Sci. 317, 93-304 (1988; Zbl 0669.68053)]. The author studies generalized zeta functions of formal power series in noncommuting variables with coefficients in a subring of the field of real numbers. It is shown that if the (generalized) zeta function of a series having coefficients in \(\mathbb{Z}\) is rational, then the power series expansion of the function has integer coefficients. As a consequence, certain necessary conditions for the rationality of the (generalized) zeta function of a language are derived. The author also shows that it is decidable whether or not the (generalized) zeta function of a \(\mathbb{Q}\)- algebraic series is a rational function. If it is rational, it can be computed effectively. As a consequence, if \(G\) is a given unambiguous context-free grammar, it is decidable whether or not the (generalized) zeta function of the language generated by \(G\) is rational. The same question is shown to be undecidable for context-free grammars.