Soutenance thèse de doctorat en Mathématiques-Informatique

Monsieur Alexandre MANSARD
Mardi 24 novembre 2020
à 14 heures (Heure Réunion)
A l'amphithéâtre Commerson (Moufia)
et
en visioconférence via ce lien :

https://univ-reunion-fr.zoom.us/j/85221035164?pwd=ZWFDMGJUVWVrUVFUVHV2MVk5eTFhQT09

ID de réunion : 852 2103 5164
Code secret : 359526

Monsieur Alexandre MANSARD soutiendra sa thèse de doctorat en Mathématiques-Informatique, intitulée "Automates infinis et traces de Mazurkiewicz", sous la direction de Monsieur Christian DELHOMMÉ et M. Didier CAUCAL

Composition du jury :

  • Monsieur Christian DELHOMMÉ, Professeur, Université de La Réunion
  • Monsieur Didier CAUCAL, Directeur de recherches, CNRS Université Gustave Eiffel
  • Monsieur Volker DIEKERT, Professeur, Universität Stuttgart
  • Monsieur Kamal LODAYA, Professeur, Indian Institute of Science
  • Monsieur Victor CHEPOI, Professeur,  Aix-Marseille Université
  • Madame Marianne MORILLON, Professeur, Université de La Réunion
  • Madame Chloé RISPAL, Maître de conférences, Université Gustave Eiffel
  • Madame Sophie TISON, Professeur, Université de Lille 1

Résumé :

Nous introduisons la notion de régularité par niveaux pour des langages de traces de Mazurkiewicz et nous considérons des systèmes reconnaissables de réécriture de traces, à contextes réguliers par niveaux (RTL). Nous prouvons qu’un automate dont le graphe sous-jacent est le graphe de réécriture d’un système RTL et dont les ensembles de sommets initiaux et finaux sont réguliers par niveaux (automate RTL), est mot-automatique. En particulier, la théorie du premier ordre d’un automate RTL est décidable. Ensuite, nous prouvons que, enrichi de la relation d’accessibilité, un automate dont le graphe sous-jacent est déplié concurrent d’un graphe fini concurrent et dont les ensembles de sommets initiaux et finaux sont réguliers par niveaux, est RTL. En particulier, la théorie du premier ordre avec accessibilité d’un tel automate est décidable. Par ailleurs, il est bien connu que la théorie du premier ordre avec accessibilité du graphe de réécriture suffixe d’un système de réécriture de termes clos (graphe GTR) est décidable. Nous mettons en évidence divers dépliés concurrents de graphes finis concurrents qui ne sont pas des graphes GTR. L’arbre du quart de la grille infinie est un exemple de tel déplié. La classe des dépliés concurrents des graphes finis concurrents constitue ainsi une classe de DAG mot-automatiques, dont la théorie du premier ordre avec accessibilité est décidable et qui contient des graphes non GTR.

Nous définissons pour les automates de traces (automates dont les sommets sont des traces de Mazurkiewicz) deux opérations que sont la synchronisation par niveaux et la superposition par niveaux et nous montrons que si une famille F d’automates de traces est fermée pour ces opérations, alors pour tout automate déterministe H 2 F, les langages acceptés par les automates déterministes de F qui sont longueur-réductibles en H forment une algèbre de Boole ; la longueur d’une trace étant donnée par la longueur de sa forme normale de Foata, un automate de traces G est longueur-réductible dans un automate de traces H, s’il existe un morphisme de G dans H préservant la longueur. Ensuite, nous montrons que la classe des automates suffixes de traces à contextes réguliers par niveaux, qui n’est que l’extension aux traces de Mazurkiewicz des automates suffixes de mots, satisfait ces propriétés de fermeture. Nous appelons réseau de Petri généralisé un automate suffixe de traces sur un alphabet de dépendance pour lequel la dépendance est réduite à l’égalité. Nous montrons alors que la sous-famille des réseaux de Petri généralisés satisfait également les propriétés de fermeture ci-dessus. Cela conduit notamment à diverses algèbres de Boole de langages acceptés par des réseaux de Petri généralisés déterministes.