Strongly locally testable semigroups with commuting idempotents and related languages
LITP, Université de Paris VII, 2 place Jussieu, 75251 Paris Cedex 05, France,
and Université de Rouen,
Département d'Informatique, place Émile Blondel,
76128 Mont-Saint-Aignan Cedex, France; firstname.lastname@example.org.
Accepted: September 1998
If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. S is strongly locally testable if whenever two words over the alphabet S have the same factors of a fixed length k, then the products of the letters of these words are equal. We had previously proved  that the syntactic semigroup of a rational language L is strongly locally testable if and only if L is both locally and piecewise testable. We characterize in this paper the variety of strongly locally testable semigroups with commuting idempotents and, using the theory of implicit operations on a variety of semigroups, we derive an elementary combinatorial description of the related variety of languages.
© EDP Sciences, 1999