Syntactic Semigroups of Languages Closed Under Factors
by
Arseny M. Shur
Ural State University, Ekaterinburg, Russia

Let us take the free semigroup A⁺ over a finite set A and a language L subset or equal A⁺. We recall that the syntactic congruence of L is defined as follows:

\piL={(U, V) in A+×A+|  for allP, Q in A+ \cup {\lambda} (PUQ in L) <===> (PVQ in L)},

where \lambda denotes the empty word; the syntactic semigroup of L is the factorsemigroup A⁺/\pi_L.

We investigate the syntactic semigroups of languages closed under factors; so the syntactic semigroups are nilsemigroups. Two classes of languages of this sort are involved. The languages generated by morphisms constitute the first class and the second one consists of languages closed under some avoidability relation (i.e. the sets of all words avoiding a given regularity). Most of our results are formulated as solutions to the word problem in semigroups of given type.

Date received: May 12, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-27.