A necessary condition for the rationality of the zeta function of a regular language
type: Item
instance of: scholarly article
title: A necessary condition for the rationality of the zeta function of a regular language
zbMATH Open document ID: 0675.68034
DOI: 10.1016/0304-3975(89)90159-X
author: Juha Honkala
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 11S40
zbMATH DE Number: 4106278
zbMATH Keywords: zeta function
zbMATH Keywords: formal language
Wikidata QID: Q56060442
reviewed by: Christophe Reutenauer
MaRDI profile type: Publication
cites work: Q4430300
cites work: Q3823156
cites work: Q4079524
cites work: Q3935355
cites work: Q3659988
cites work: Q3948608
cites work: Q4155837
cites work: On generalized zeta functions of formal languages and series
description: scientific article; zbMATH DE number 4106278