# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Zeta functions of formal languages. (English) Zbl 0797.68092

The authors define the zeta function $\zeta \left(L\right)$ of a language $L$ by $\zeta \left(L\right)=exp\left({\sum }_{n\ge 1}{a}_{n}{t}^{n}/n\right)$, where ${a}_{n}$ is the number of words of length $n$ in $L$. They define the generalized zeta function $Z\left(S\right)$ of a formal power series $S$ in noncommuting variables by $Z\left(S\right)=exp\left({\sum }_{n\ge 1}\pi \left({S}_{n}\right)/n\right)$, where $\pi \left({S}_{n}\right)$ is the homogeneous part of degree $n$ of $S$ viewed in a canonical way as a formal series in commuting variables. The generalized zeta function of a language $L$ is $Z\left(\underline{L}\right)$, where $\underline{L}$ is the characteristic series of $L$. By definition, a language $L$ is cyclic if (i) $uv\in L$ if and only if $vu\in L$ and (ii) $w\in L$ if and only if ${w}^{n}\in L$ $\left(n\ge 1\right)$. The authors show that if $L$ is a cyclic language then $\zeta \left(L\right)={\prod }_{n\ge 1}{\left(1-{t}^{n}\right)}^{-{\alpha }_{n}}$, where ${\alpha }_{n}$ is the number of conjugation classes of primitive words of length $n$ contained in $L$. If $𝒜$ is a finite automaton over $A$, the trace $\text{tr}\left(𝒜\right)$ of $𝒜$ is the formal power series $\text{tr}\left(𝒜\right)={\sum }_{w\in {A}^{*}}{\alpha }_{w}w$, where ${\alpha }_{w}$ is the number of couples $\left(q,c\right)$ such that $q$ is a state of $𝒜$ and $c$ is a path $q\to q$ in $𝒜$ labelled $w$. The authors prove that $Z\left(\text{tr}\left(𝒜\right)\right)$ is rational. Using the theory of minimal ideals in finite semigroups, they are able to show that the characteristic series of a cyclic recognizable language is a linear combination over $ℤ$ of traces of finite deterministic automata. Consequently, if $L$ is cyclic and recognizable then $\zeta \left(L\right)$ and $Z\left(L\right)$ are rational. As a corollary the authors obtain the rationality of the zeta function of a sofic system in symbolic dynamics. The authors discuss connections to Dwork’s theorem stating that the zeta function of an algebraic variety over a finite field is rational.

This remarkable paper opens up new and interesting research areas.

##### MSC:
 68Q45 Formal languages and automata 20M35 Semigroups in automata theory, linguistics, etc. 05A15 Exact enumeration problems, generating functions 37-99 Dynamic systems and ergodic theory (MSC2000) 14G10 Zeta-functions and related questions 37C25 Fixed points, periodic points, fixed-point index theory 68Q70 Algebraic theory of languages and automata