×

A class of formal languages. (English. Russian original) Zbl 0917.20056

Algebra Logika 37, No. 4, 478-492 (1998); translation in Algebra Logic 37, No. 4, 270-277 (1998).
The authors deal with languages \(L\) that are classes of fully invariant congruences on free semigroups \(A^+\) of finite rank over a finite alphabet \(A\). The question is posed as to whether a given fully invariant congruence coincides with a syntactic congruence of the language in question. For a two-letter alphabet \(A=\{a,b\}\), suppose \(TM\) is the language consisting of all Thue-Morse words and of their subwords, and \(\overline{TM}\) is its complement in \(A^+\). The syntactic congruence of the language \(\overline{TM}\) is proven to be equal to the Riesz congruence up to the ideal \(\overline{TM}\). If all classes of a given fully invariant congruence are rational languages, the corresponding variety is said to be rational. Some properties of rational varieties are established. For 0-reduced semigroup varieties (i.e. varieties given by identities of the form \(W=0\)) and varieties of periodic semigroups satisfying an identity of the form \( x_1\cdots x_n=f(x_1,\ldots,x_n)\), it is proven that the variety is rational if and only if it is locally finite.

MSC:

20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
20M07 Varieties and pseudovarieties of semigroups
68Q45 Formal languages and automata
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: EuDML