Over Testable Languages

C. Selmi

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

PostScript : Ko /Kb

Titre / Title: Over Testable Languages

Résumé : Nous donnons une description combinatoire de la variété de langages qui sont à la fois localement testables et testables par morceaux , langages que nous appelons plus que testables.
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 caractérisons la variété des semigroupes fortement localement testables en démontrant que elle coïncide avec l'intersection de la variété des semigroupes localement idempotents et commutatifs et celle des semigroupes J-triviaux. D'après cette égalité, un langage est plus que que testables si et seulement si son semigroupes syntaxique est fortement localement testable. En utilisant cette caract'erisation algébrique, nous obtenons une description combinatoire assez élémentaire de la variéte de langages plus que testables.

Abstract : In this paper we give a combinatorial description of the languages that are both locally and piecewice testable.
We call such languages over testable. The locally testable semigroups were discovered in the study of finite automata. 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.

Publications internes Litp 1994 / Litp research reports 1994