Le problème du tri généralisé, un point de vue symbolique à propos des algorithmes réversibles

Nous présentons un cadre pour associer de manière originale et naturelle, un algorithme à un ensemble de règles de réécriture. Ici un algorithme est identifié avec l’ensemble de ses traces d’exécution. Les systèmes de réécriture sont définis sur les séquences de transformations élémentaires et sont tels que leurs formes normales sont exactement les traces d’exécution.

Les algorithmes que nous considérons sont ceux qui cherchent à résoudre une classe de problèmes que nous introduisons sous le nom des problèmes de tri généralisé. Il s’agit de la recherche d’une séquence génératrice particulière pour une algèbre présentée. Sous des hypothèses raisonnables, nous montrons que les traces d’exécution de ces algorithmes sont des diagrammes (i.e., graphes orientés et arc-colorés) couvrants des diagrammes de Cayley du groupe des automorphismes de l’algèbre présentée associé à l’algorithme (et donc des systèmes de réécriture).

En utilisant le formalisme des ASM introduit par Gurevich, nous montrons que tout algorithme qui est réversible (i.e., qui ne perd pas d’information durant une exécution) et qui s’arrête toujours, résout un problème de tri généralisé. Notre approche permet de relier dans les cas très simples une borne inférieure de complexité au diamètre d’un graphe de Cayley.