*(English)*Zbl 0797.68092

The authors define the zeta function $\zeta \left(L\right)$ of a language $L$ by $\zeta \left(L\right)=exp({\sum}_{n\ge 1}{a}_{n}{t}^{n}/n)$, 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({\sum}_{n\ge 1}\pi \left({S}_{n}\right)/n)$, 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$ $(n\ge 1)$. The authors show that if $L$ is a cyclic language then $\zeta \left(L\right)={\prod}_{n\ge 1}{(1-{t}^{n})}^{-{\alpha}_{n}}$, where ${\alpha}_{n}$ is the number of conjugation classes of primitive words of length $n$ contained in $L$. If $\mathcal{A}$ is a finite automaton over $A$, the trace $\text{tr}\left(\mathcal{A}\right)$ of $\mathcal{A}$ is the formal power series $\text{tr}\left(\mathcal{A}\right)={\sum}_{w\in {A}^{*}}{\alpha}_{w}w$, where ${\alpha}_{w}$ is the number of couples $(q,c)$ such that $q$ is a state of $\mathcal{A}$ and $c$ is a path $q\to q$ in $\mathcal{A}$ labelled $w$. The authors prove that $Z\left(\text{tr}\right(\mathcal{A}\left)\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 $\mathbb{Z}$ 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 |