Zeta functions of formal languages

Berstel, Jean; Reutenauer, Christophe

doi:10.1090/S0002-9947-1990-0998123-X

Zeta functions of formal languages
HTML articles powered by AMS MathViewer

by Jean Berstel and Christophe Reutenauer PDF

Trans. Amer. Math. Soc. 321 (1990), 533-546 Request permission

Abstract:

Motivated by symbolic dynamics and algebraic geometry over finite fields, we define cyclic languages and the zeta function of a language. The main result is that the zeta function of a cyclic language which is recognizable by a finite automation is rational.

References

Puissance extérieure d’un automate déterministe: application au calcul de la fonction zeta d’un système sofique

Danièle Beauquier, Minimal automaton for a factorial, transitive, and rational language, Theoret. Comput. Sci. 67 (1989), no. 1, 65–73. MR 1015085, DOI 10.1016/0304-3975(89)90022-4
Jean Berstel and Dominique Perrin, Theory of codes, Pure and Applied Mathematics, vol. 117, Academic Press, Inc., Orlando, FL, 1985. MR 797069
Jean Berstel and Christophe Reutenauer, Rational series and their languages, EATCS Monographs on Theoretical Computer Science, vol. 12, Springer-Verlag, Berlin, 1988. MR 971022, DOI 10.1007/978-3-642-73235-5
R. Bowen and O. E. Lanford III, Zeta functions of restrictions of the shift transformation, Global Analysis (Proc. Sympos. Pure Math., Vol. XIV, Berkeley, Calif., 1968) Amer. Math. Soc., Providence, R.I., 1970, pp. 43–49. MR 0271401
Rufus Bowen, On Axiom A diffeomorphisms, Regional Conference Series in Mathematics, No. 35, American Mathematical Society, Providence, R.I., 1978. MR 0482842
N. Chomsky and M. P. Schützenberger, The algebraic theory of context-free languages, Computer programming and formal systems, North-Holland, Amsterdam, 1963, pp. 118–161. MR 0152391
Ethan M. Coven and Michael E. Paul, Sofic systems, Israel J. Math. 20 (1975), no. 2, 165–177. MR 383379, DOI 10.1007/BF02757884
Bernard Dwork, On the rationality of the zeta function of an algebraic variety, Amer. J. Math. 82 (1960), 631–648. MR 140494, DOI 10.2307/2372974
Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382
David Fried, Finitely presented dynamical systems, Ergodic Theory Dynam. Systems 7 (1987), no. 4, 489–507. MR 922362, DOI 10.1017/S014338570000417X
Solomon W. Golomb, Irreducible polynomials, synchronization codes, primitive necklaces, and the cyclotomic algebra, Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967) Univ. North Carolina Press, Chapel Hill, N.C., 1969, pp. 358–370. MR 0248115
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157
Juha Honkala, A necessary condition for the rationality of the zeta function of a regular language, Theoret. Comput. Sci. 66 (1989), no. 3, 341–347. MR 1018569, DOI 10.1016/0304-3975(89)90159-X
Juha Honkala, On generalized zeta functions of formal languages and series, Discrete Appl. Math. 32 (1991), no. 2, 141–153. MR 1120666, DOI 10.1016/0166-218X(91)90097-G
Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR 661047
Neal Koblitz, $p$-adic numbers, $p$-adic analysis, and zeta-functions, 2nd ed., Graduate Texts in Mathematics, vol. 58, Springer-Verlag, New York, 1984. MR 754003, DOI 10.1007/978-1-4612-1112-9
Gérard Lallement, Semigroups and combinatorial applications, Pure and Applied Mathematics, John Wiley & Sons, New York-Chichester-Brisbane, 1979. MR 530552
Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. MR 675953
Anthony Manning, Axiom $\textrm {A}$ diffeomorphisms have rational zeta functions, Bull. London Math. Soc. 3 (1971), 215–220. MR 288786, DOI 10.1112/blms/3.2.215
Masakazu Nasu, Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs, Discrete Math. 39 (1982), no. 2, 171–197. MR 675863, DOI 10.1016/0012-365X(82)90141-8
Christophe Reutenauer, Séries formelles et algèbres syntactiques, J. Algebra 66 (1980), no. 2, 448–483 (French, with English summary). MR 593604, DOI 10.1016/0021-8693(80)90097-6
Christophe Reutenauer, Semisimplicity of the algebra associated to a biprefix code, Semigroup Forum 23 (1981), no. 4, 327–342. MR 638577, DOI 10.1007/BF02676657
Christophe Reutenauer, Ensembles libres de chemins dans un graphe, Bull. Soc. Math. France 114 (1986), no. 2, 135–152 (French, with English summary). MR 860813
Christophe Reutenauer, Mots circulaires et polynômes irréductibles, Ann. Sci. Math. Québec 12 (1988), no. 2, 275–285 (French, with English summary). MR 978459
Marcel-Paul Schützenberger, Sur certains sous-monoïdes libres, Bull. Soc. Math. France 93 (1965), 209–223 (French). MR 190253
Benjamin Weiss, Subshifts of finite type and sofic systems, Monatsh. Math. 77 (1973), 462–474. MR 340556, DOI 10.1007/BF01295322