Le problème d'isomorphisme semi-groupe inverse fini est-il GI-complet?

Le problème d'isomorphisme semi - groupe inverse fini est -il GI-complet ? Ici, les semi-groupes inverses finis sont supposés être donnés par leurs tables de multiplication.

Oui, le problème d'isomorphisme de semi-groupe inverse fini est GI-complet! Ceci est un corollaire de

Théorème: l' isomorphisme du réseau est l'isomorphisme complet

de la section 7.2 Réseaux et posets

Booth, Kellogg S .; Colbourn, CJ (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo.

car un (semi-) réseau est aussi un semi-groupe inverse (commutatif idempotent).

Preuve du théorème du rapport technique:

Il suffit de représenter un graphe uniquement comme un réseau. Étant donné un graphe avec sommets et arêtes, nous définissons un réseau avec un élément pour chaque sommet, un élément pour chaque arête, et deux éléments supplémentaires et . L'élément domine tous les autres (le supremum ), et l'élément est dominé par tous les autres éléments (l' infimum ). Une arête domine exactement les sommets qui en sont les extrémités. Le résultat est un réseau unique qui représente .$G$$n$$m$$\text{'}0\text{'}$$\text{'}1\text{'}$$\text{'}1\text{'}$$\text{'}0\text{'}$$G$

L'idée de cette réponse est venue d'une discussion avec vzn sur des questions suffisamment ciblées . La motivation à passer du temps sur l'isomorphisme graphique est également venue de la répétition de vzn. J.-E. Pin a demandé dans le commentaire s'il y avait des raisons spécifiques d'envisager des semi-groupes inverses. L'idée était d'avoir une structure de groupes légèrement généralisante, qui est GI complète. Je voulais mieux comprendre la relation entre l' isomorphisme de groupe et l' isomorphisme de graphe, mais je crains que cette réponse ne donne aucun aperçu de ce genre.