The authors define the zeta function of a language by , where is the number of words of length in . They define the generalized zeta function of a formal power series in noncommuting variables by , where is the homogeneous part of degree of viewed in a canonical way as a formal series in commuting variables. The generalized zeta function of a language is , where is the characteristic series of . By definition, a language is cyclic if (i) if and only if and (ii) if and only if . The authors show that if is a cyclic language then , where is the number of conjugation classes of primitive words of length contained in . If is a finite automaton over , the trace of is the formal power series , where is the number of couples such that is a state of and is a path in labelled . The authors prove that 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 is cyclic and recognizable then and 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.