Sukhanov, E. V.; Shur, A. M. 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. Reviewer: A.N.Ryaskin (Novosibirsk) 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 Keywords:free semigroups; rational languages; fully invariant congruences; syntactic congruences; Thue-Morse words; rational semigroup varieties; locally finite varieties of semigroups PDFBibTeX XMLCite \textit{E. V. Sukhanov} and \textit{A. M. Shur}, Algebra Logika 37, No. 4, 478--492 (1998; Zbl 0917.20056); translation in Algebra Logic 37, No. 4, 270--277 (1998) Full Text: EuDML