next previous contents


Next: Topologie profinie Up: Home Page Previous: Langages reconnaissables


Produit de concaténation et hiérarchies

Le produit de concaténation, qui est le produit naturel sur les mots, est l'une des opérations les plus riches de la théorie des langages. Comme pour la hauteur d'étoile, on construit en effet de façon très naturelle des hiérarchies en alternant, dans la construction des langages, opérations booléennes et produit. L'étude de ces hiérarchies, entamée depuis près de vingt ans, a pris une nouvelle envergure depuis quelques années. On sait en effet construire des hiérarchies parallèles de variétés de semigroupes d'une part et de formules logiques d'autre part et ces hiérarchies se correspondent niveau par niveau. On a donc trois angles d'attaque différents : combinatoire, algébrique et logique, ce qui donne une théorie fascinante où un succès dans l'une des approches est immédiatement exploité par les deux autres. S'y ajoute dans certains cas une approche topologique dont je reparle plus loin.

Plusieurs outils algébriques peuvent être utilisés pour étudier le produit de concaténation. J'ai amélioré en [52] puis en [83] un résultat de Straubing sur les liens entre les semigroupes syntactiques de n langages et le semigroupe syntactique de leur produit.

Straubing avait caractérisé en termes de variétés de semigroupes le produit de concaténation (défini sur les langages). La démonstration de ce résultat utilisait des techniques difficiles issues de la théorie des produits en couronne (travaux de Rhodes, Tilson, etc...). J'ai proposé une démonstration entièrement différente de ce résultat, basée d'une part sur un algorithme de Schützenberger et d'autre part sur une utilisation systématique des morphismes relationnels entre semigroupes, dont j'ai donné par ailleurs les propriétés fondamentales [10]. La même méthode permet alors de caractériser la fermeture par produit non ambigu ou déterministe [13]. Ces résultats permettent en outre de retrouver comme cas particuliers plusieurs théorèmes de Brzozowski, Eilenberg, Perrin et Schützenberger . Ultérieurement, j'ai obtenu, avec H. Straubing et D. Thérien, des résultats analogues par une autre technique [54]. J'ai aussi étudié, avec D. Thérien [80], le produit bidéterministe, une variante du produit elle aussi introduite par Schützenberger. L'un de mes étudiants, M. Branco, a depuis amélioré et généralisé ces résultats et prépare une thèse sur ce thème.

J'ai beaucoup contribué à l'étude des hiérarchies de concaténation [19,24,25,45,83]. J'ai montré que toutes les hiérarchies considérées jusqu'à présent étaient des cas particuliers d'une hiérarchie indexée par des arbres [35]. J'ai par ailleurs introduit les "demi-niveaux" de la hiérarchie [45,83] dont l'idée est toute simple : on part d'une famille de langages qui constitue le niveau 0. Pour passer du niveau n au niveau n + 1/2, on applique l'union et le produit. Pour passer du niveau n + 1/2 au niveau n+1 on applique les opérations booléennes (union, intersection, complément). J'ai démontré que les hiérarchies de langages correspondaient à une hiérarchie parallèle de variétés de semigroupes (semigroupes ordonnés si on prend en compte les demi-niveaux). J'ai pu établir la décidabilité d'une sous-hiérarchie introduite par I. Simon et j'ai également exploré la hiérarchie de Straubing, en particulier le niveau 2 de cette hiérarchie, dont la décidabilité n'a pu être encore établie en toute généralité. J'ai montré avec H. Straubing que ce problème était équivalent d'une part au problème de la décidabilité de la variété PJ - ce qui établit un lien inattendu avec l'opérateur P - et d'autre part avec un problème de pure théorie des semigroupes : peut-on décider si un semigroupe fini divise un semigroupe de matrice booléennes triangulaires ? Par ailleurs, les travaux de W. Thomas ont montré l'équivalence de ces problèmes avec un problème de décidabilité en logique du premier ordre. Ce problème est, à ce jour, non encore résolu.

L'article [83], écrit conjointement avec P. Weil, contient plusieurs résultats majeurs qui constituent une percée sur le thème. On y décrit notamment une opération algébrique pour passer du niveau n au niveau n + 1/2. Ce résultat permet de démontrer la décidabilité du niveau 3/2 et fournit un algorithme polynomial pour ce problème. Par ailleurs, nous montrons que les langages qui sont de niveau n + 1/2 et dont le complémentaire est de niveau n + 1/2 peuvent en fait s'obtenir à partir du niveau n par union et produit non ambigu. Ce résultat difficile, qui présente des analogies avec des résultats de théorie descriptive des ensembles a des conséquences très intéressantes en logique (voir ci-dessous).

J'ai également étudié, avec Margolis, les hiérarchies de concaténation issues des langages à groupe [41]. La résolution récente de la conjecture de Rhodes (voir plus loin) a permis de donner une caractérisation effective des niveaux 1/2 et 1 de cette hiérarchie [66,83]. Cette hiérarchie est étroitement reliée à la topologie des groupes finis.



next up previous contents

Next: Topologie profinie Up: Home Page Previous: Langages reconnaissables


Jean-Éric PIN, 5 Octobre 1996