• Langue : Français
• Discipline : Informatique
• Identifiant : Inconnu
• Type de thèse : Doctorat
• Date de soutenance : 01/01/1984

Résumé en langue originale

Nous définissons des fonctions de commutation sur les mots par la donnée d'une relation binaire quelconque sur un alphabet ; les fonctions de semi-commutation correspondent aux relations non réflexives, les fonctions de commutation partielle sont associées aux relations non réflexives et symétriques, et dans le cas où la relation est le complémentaire d'une relation d'équivalence, nous obtenons les fonctions de commutation partitionnée. Ce dernier type de fonction a l'avantage de s'exprimer facilement au moyen d'opérations bien connues : les homomorphismes et l'opération de shuffle. Nous montrons alors qu'on peut factoriser les fonctions de commutation partielle et les fonctions de semi-commutation en une succession d'homomorphismes, d'hmomorphismes inverses et de fonctions de commutation partitionnée. Puis nous étudions les propriétés des cônes rationnels fidèles clos par commutation partielle, ce qui nous permet d'obtenir une nouvelle caractérisation de la famille des langages Multireset qui est le plus petit cône rationnel fidèle clos par commutation partielle. Nous montrons que la hiérarchie des familles de langages construite à partir des langages rationnels au moyen des fonctions de semi-commutation (resp. commutation partielle, commutation partitionnée) est une hiérarchie infinie. Enfin, nous étudions les problèmes de décidabilité concernant principalement P(rat), la famille des langages images par une fonction de commutation partitionnée d'un langage rationnel.