×

A necessary condition for the rationality of the zeta function of a regular language. (English) Zbl 0675.68034

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.
Reviewer: Ch.Reutenauer

MSC:

68Q70 Algebraic theory of languages and automata
68Q45 Formal languages and automata
11S40 Zeta functions and \(L\)-functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel, J.; Perrin, D., The Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[2] Berstel, J.; Reutenauer, C., Zeta functions of recognizable languages, (Lepistö, T.; Salomaa, A., Automata, Languages and Programming (1988), Springer: Springer Berlin), 93-104 · Zbl 0669.68053
[3] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[4] Knuth, D., The Art of Computer Programming, Vol. 2, Seminumerical Algorithms (1981), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0477.65002
[5] Koblitz, N., p-Adic Numbers, p-Adic Analysis and Zeta-Functions (1984), Springer: Springer Berlin
[6] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[7] Salomaa, A., Jewels of Formal Language Theory (1981), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0487.68063
[8] Salomaa, A.; Soittola, M., Automata-Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
[9] J. Honkala, On generalized zeta functions of formal languages and series, submitted.; J. Honkala, On generalized zeta functions of formal languages and series, submitted. · Zbl 0744.68075
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.