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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]