A necessary condition for the rationality of the zeta function of a regular language (Q1122359): Difference between revisions
From MaRDI portal
Created a new Item |
Created claim: Wikidata QID (P12): Q56060442, #quickstatements; #temporary_batch_1704771653347 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56060442 / rank | |||
Normal rank |
Revision as of 05:43, 9 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A necessary condition for the rationality of the zeta function of a regular language |
scientific article |
Statements
A necessary condition for the rationality of the zeta function of a regular language (English)
0 references
1989
0 references
The zeta function of a formal language L is the series exp(\(\sum_{n\geq 1}a_ nx^ n/n)\), where \(a_ n\) is the number of words of length n in L. The author shows that if L is regular and if its zeta function is regular, then it has integer coefficients and each irreducible factor of its numerator and denominator divides the denominator of the generating function \(\sum_{n\geq 0}a_ nx^ n\) of L (which is rational, L being regular). He shows, under the same hypothesis, that there are cyclic languages \(L_ 1\) and \(L_ 2\) such that the generating function G(L) of L is \(G(L_ 1)-G(L_ 2)\) (a language is cyclic if (i) uv\(\in L\Leftrightarrow vu\in L\) and (ii) \(w\in L\Leftrightarrow w^ n\in L\) (n\(\geq 1))\). Moreover, it is decidable whether the zeta function of a regular language is rational.
0 references
zeta function
0 references
formal language
0 references