Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

# Simple Search

Query:
Enter a query and click »Search«...
Format:
Display: entries per page entries
Zbl 0797.68092
Berstel, Jean; Reutenauer, Christophe
Zeta functions of formal languages.
(English)
[J] Trans. Am. Math. Soc. 321, No.2, 533-546 (1990). ISSN 0002-9947; ISSN 1088-6850/e

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.\par This remarkable paper opens up new and interesting research areas.
MSC 2000:
*68Q45 Formal languages
20M35 Semigroups in automata theory, linguistics, etc.
05A15 Combinatorial enumeration problems
37-99 Dynamic systems and ergodic theory
14G10 Zeta-functions and related questions
37C25 Fixed points, periodic points, fixed-point index theory
68Q70 Algebraic theory of automata

Keywords: formal languages; algebraic geometry over finite fields; rationality of zeta function; zeta function; formal power series; cyclic language; minimal ideals in finite semigroups; characteristic series; cyclic recognizable language; traces of finite deterministic automata; sofic system; symbolic dynamics

Cited in: Zbl 0876.68068

Highlights
Master Server