Décidabilité de l'appartenance à la variété de langages engendrée par les langages testables par morceaux et les langages de bandes

M. ZEITOUN

IBP-Litp 1994/06: Rapport de Recherche Litp / Litp research reports
25 pages - Décembre/December 1994 - French document.

PostScript : Ko /Kb

Titre / Title: Décidabilité de l'appartenance à la variété de langages engendrée par les langages testables par morceaux et les langages de bandes

Résumé : Le but de cet article est de prouver que la variété engendrée par les langages testables par morceaux et les langages de bandes est décidable. En d'autres termes, nous prouvons la décidabilité de la pseudo-variété engendrée par J»B, c'est-à-dire, le supremum de la pseudo-variété des semigroupes J-triviaux et celle des semigroupes idempotents. Les techniques utilisées ont été développées par Almeida et sont basées sur l'étude du semigroupe topologique des opérations implicites.

Abstract : The aim of this article is to prove that the variety generated by the piecewise testable languages and the band languages est décidable. In other words, we show that the pseudovariety generated par J»B, that is to say, the join of the pseudovariety of J-trivial semigroups and of the one of idempotent semigroups, is decidable. The techniques used were treated by Almeida and are based on the study of the study of the topological semigroup of implicit operations.

Publications internes Litp 1994 / Litp research reports 1994