zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Zeta functions of formal languages. (English) Zbl 0797.68092
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.

68Q45Formal languages and automata
20M35Semigroups in automata theory, linguistics, etc.
05A15Exact enumeration problems, generating functions
37-99Dynamic systems and ergodic theory (MSC2000)
14G10Zeta-functions and related questions
37C25Fixed points, periodic points, fixed-point index theory
68Q70Algebraic theory of languages and automata
Full Text: DOI