Commutative Over Testable Languages

C. Selmi

IBP-Litp 1994/40: Rapport de Recherche Litp / Litp research reports
20 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Commutative Over Testable Languages

Résumé : Zalcstein a introduit la notion de semigroupe localement testable. Si l'on considère l'ensemble des mots sur l'alphabet constitué par les éléments d'un semigroupe S, alors tout mot u appartenant à cet ensemble détermine un élément de S: le produit des lettres de u. Un semigroupe S est localement testable si deux mots sur l'alphabet S qui ont le même enseble de facteurs d'une longueur fixée k, le même préfixe et le même suffixe de longueur k-1, déterminent le même produit. On obtient une géneralisation très naturelle de la notion de semigroupe localement testable en supprimant la condition sur les préfixes et les suffixes. On appelle fortement localement testable un semigroupe de ce type. Nous avons prouvé que le semigroupe syntaxique d'un langage L est fortement localement testable si et seulement si L est à la fois localement testable et testable par morceaux. Nous appellons ces langages plus que testables. Nous caractérisons dans ce travail la variété de semigroupes fortement localement testables dont les idempotents commutent. En utilisant cette caract'erisation algébrique et la théorie des opérations implicites sur les variétés des semigroupes, nous obtenons une description combinatoire assez élémentaire de la variéte de langages associée. Langages que nous appellons plus que testables commutatifs.

Abstract : The locally testable semigroups are studied by Zalcstein and they are related with the notion of locally testable language. The definition is the following: if we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determine an element of S: the product of the letters of the word. A semigroup S is locally testable if whenever two words over the alphabet S having the same factors of a fixed length k and the same prefix and suffix of length k-1, then the products of the letters of these words are equal. A natural extension of locally testable semigroups is obtained by dropping the condition about prefix and suffix. We call semigroups of this type strongly locally testable. We have 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. These languages are called over testable. We characterize in this paper the variety of the 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. These languages will be called commutative over testable.

Publications internes Litp 1994 / Litp research reports 1994