Machines de Mealy, (semi-)groupes d'automate, problèmes de décision et génération aléatoire – MealyM

Ce projet a pour objet les (semi-)groupes d'automate, c'est-à-dire les (semi-)groupes engendrés par des machines de Mealy. Cette possibilité de présentation pour des (semi-)groupes a été jusqu'à maintenant principalement étudiée par des mathématiciens via la théorie géométrique des groupes. Elle n'a pas encore été exploitée par la communauté informatique bien qu'elle permette d'obtenir des groupes très sophistiqués à partir d'objets petits et simples qui justement se trouvent être largement utilisés et étudiés en informatique.

La progression se fera le long de deux axes entrelacés.

Nous avons l'intention d'obtenir des résultats théoriques sur les (semi-)groupes d'automate en utilisant des techniques informatiques, répondant principalement à des problèmes de décision de manière efficace: une machine de Mealy donnée engendre-t-elle un (semi-)groupe fini ou infini? Quel est l'ordre d'un élément du groupe d'automate donné? Etc.

Notre objectif est de développer des outils efficaces pour engendrer aléatoirement des (semi-)groupes via des machines de Mealy aléatoires.
La génération aléatoire est une procédure classique permettant de vérifier la robustesse des programmes, de faire des simulations numériques ou de tester des conjectures.


Les résultats obtenus dans chacune des deux directions seront implémentés dans Sage, soit directement soit via GAP.


Afin de favoriser une intensive collaboration entre les membres du projet, nous prévoyons de:

- ponctuer le projet par des journées d'équipe sur une base trimestrielle,
- financer 15 mois de gratification pour des stages de master
- accueillir des experts internationaux (visite longue) et des jeunes chercheurs et chercheuses,
- organiser une rencontre principale durant la quatrième année du projet, réunissant une trentaines de personnes, étudiants en master ou post-docs et chercheurs confirmés, pour une semaine d'intenses discussions sur des problèmes de recherche,
- financer une thèse qui sera co-encadrée par les deux chefs d'équipe (I. Klimann et M. Picantin): le doctorant travaillera à temps plein sur le projet.