On generalized zeta functions of formal languages and series
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.
- Zeta Functions of Formal Languages
- A necessary condition for the rationality of the zeta function of a regular language
- On algebraic generalized zeta functions of formal power series
- scientific article; zbMATH DE number 1229927
- A representation theorem of infinite dimensional algebras and applications to language theory
- scientific article; zbMATH DE number 4096799
- scientific article; zbMATH DE number 1754620
- The zig-zag power series: A two-way version of the \({}^*\) operator.
- scientific article; zbMATH DE number 7300346
- Transcendence of formal power series with rational coefficients
- A necessary condition for the rationality of the zeta function of a regular language
- An Approach to a Unified Theory of Automata
- scientific article; zbMATH DE number 4170851 (Why is no real title available?)
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 3932372 (Why is no real title available?)
- scientific article; zbMATH DE number 4096799 (Why is no real title available?)
- scientific article; zbMATH DE number 41838 (Why is no real title available?)
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- scientific article; zbMATH DE number 3413820 (Why is no real title available?)
- On the Rationality of the Zeta Function of an Algebraic Variety
- A necessary condition for the rationality of the zeta function of a regular language
- Regular languages and their generating functions: The inverse problem
- scientific article; zbMATH DE number 4096799 (Why is no real title available?)
- Zeta Functions of Formal Languages
- On algebraic generalized zeta functions of formal power series
This page was built for publication: On generalized zeta functions of formal languages and series
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179183)
