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; selmi@dir.univ-rouen.fr.

Received: July 1994
Accepted: September 1998

Abstract

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 [19] 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.