thesis

Langages et semi groupes testables

Defense date:

Jan. 1, 1994

Edit

Institution:

Paris 7

Disciplines:

Authors:

Directors:

Abstract EN:

Pas de résumé disponible.

Abstract FR:

La recherche d'une description combinatoire de la variete de langages qui sont a la fois localement testables et testables par morceaux fait l'objet de cette these. On appelle plus que testable un langage de ce type. Un semigroupe localement testable est un semigroupe qui verifie des proprietes qui evoquent la definition de langage localement testable. Les semigroupes fortement localement testables representent une generalisation de cette notion que l'on obtient en supprimant les conditions sur les prefixes et les suffixes. On montre dans ce travail que l'ensemble de semigroupes fortement localement testables constitue une variete de semigroupes et qu'un langage est plus que testable si et seulement si son semigroupe syntaxique est fortement localement testable. En utilisant cette caracterisation syntaxique, on donne un ensemble de generateurs pour la variete des langages plus que testables et pour la variete de langages associee a la variete de semigroupes fortement localement testables dont les idempotents commutent. Les techniques utilisees font appel a des theories des operations implicites sur une variete de semigroupes, des systemes de reecriture et des graphes et a la combinatoire des mots