Rational languages and the Burnside problem (Q1079380)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Rational languages and the Burnside problem |
scientific article |
Statements
Rational languages and the Burnside problem (English)
0 references
1985
0 references
This survey paper is mainly concerned with the following problem: give properties which characterize regularity of formal languages. Since regularity of a language is equivalent to the finiteness of its syntactic monoid, this problem is related to the Burnside problem for monoids: under the assumption that each cyclic submonoid of the monoid M is finite (i.e. M is periodic), when M is finite ? Periodicity is itself related to the classical language-theoretic property of pumping. We consider also bounded and commutative languages in this paper, which ends with similar questions on formal power series: rationality questions, boundedness of the support.
0 references
regular languages
0 references
finiteness conditions
0 references
survey
0 references
syntactic monoid
0 references
Periodicity
0 references
pumping
0 references
formal power series
0 references