Résumé : Nous introduisons une classe de problèmes appelés recherche de représentant. Étant donné un groupe G qui opère sur un ensemble X, l'entrée d'un problème sera un élément x de X et la sortie un représentant x* de l'orbite de l'orbite de x sous l'action de G. Nous spécifions un rapport bien particulier entre X et G, qui permet, en utilisant le formalisme introduit par Gurevich pour modéliser les algorithmes, de dire que tout algorithme réversible (dans le sens où toute donnée accessible au début d'une exécution est accessible jusqu'à la fin) résout en fait un tel problème. Nous montrons que les traces d'exécution d'un tel algorithme est un diagramme (i.e., graphes orientés et arc-colorés) couvrant du diagramme de Cayley du groupe des automorphismes d'une algèbre naturellement associée à l'algorithme. Notre approche permet de relier borne inférieure de complexité et diamètre d'un graphe de Cayley du groupe d'automorphisme, lorsque ce groupe est fini. Quand il est infini, mais à croissance polynomiale, notre approche fournit, sous une condition raisonnable, une borne inférieure exponentielle, pour la complexité algébrique (i.e. on compte le nombre d'opérations élémentaires). Si le temps le permet, nous parlerons également de la caractérisation du langage des traces d'exécution d'un algorithme.

 [Slides.pdf] [vidéo]

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr