The authors define the zeta function $\zeta(L)$ of a language $L$ by $\zeta(L)= \exp (\sum\sb{n\geq 1} a\sb n t\sp n/n)$, where $a\sb n$ is the number of words of length $n$ in $L$. They define the generalized zeta function $Z(S)$ of a formal power series $S$ in noncommuting variables by $Z(S)=\exp (\sum\sb{n\geq 1} \pi(S\sb n)/n)$, where $\pi(S\sb n)$ 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(\underline {L})$, 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\sp n\in L$ $(n\geq 1)$. The authors show that if $L$ is a cyclic language then $\zeta(L)= \prod\sb{n\geq 1} (1-t\sp n)\sp{-\alpha\sb n}$, where $\alpha\sb n$ is the number of conjugation classes of primitive words of length $n$ contained in $L$. If ${\cal A}$ is a finite automaton over $A$, the trace $\text{tr}({\cal A})$ of ${\cal A}$ is the formal power series $\text{tr}({\cal A})= \sum\sb{w\in A\sp*} \alpha\sb w w$, where $\alpha\sb w$ is the number of couples $(q,c)$ such that $q$ is a state of ${\cal A}$ and $c$ is a path $q\to q$ in ${\cal A}$ labelled $w$. The authors prove that $Z(\text{tr} ({\cal A}))$ 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 $\bbfZ$ of traces of finite deterministic automata. Consequently, if $L$ is cyclic and recognizable then $\zeta(L)$ and $Z(L)$ 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 |