RAIRO - Theoretical Informatics and Applications

Research Article

Strongly locally testable semigroups with commuting idempotents and related languages

Carla Selmi

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.


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.

(Received July 1994)

(Accepted September 1998)

(Online publication August 15 2002)