Université Lille1 - Sciences et Technologies Commutations partielles et familles de langages Partial switching and language families 005.131 Langages formels Classification Parallélisme (informatique) Homomorphismes (mathématiques) Commutation (linguistique) Text Electronic Thesis or Dissertation fr 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1984/50376-1984-294.pdf Clerbout Mireille 1900-01-01 111696607 1984-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui Latteux Michel 115258817 ddc:000 ASCII PDF 9999