/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * Inverses.c Jean-Eric Pin 13/04/97 * On cree les tableaux Inverses et InversesFaibles. Pour chaque element s, * Inverses[s] contient la liste des inverses de s et InversesFaibles[s] * contient la liste des inverses faibles qui ne sont pas inverses de s. * L'algorithme ci-dessous devra etre ameliore pour eviter de faire un * parcours pour CHAQUE t dans S. * Algorithme : pour chaque t dans S, on fait un parcours en profondeur * du graphe du preordre <=J issu de t. Pour chaque s sur ce parcours, * on a s <=J t par construction et on teste si * (1) st est idempotent * (2) st R s * (3) s J t * Si (1) et (2) sont remplies, on a st = e, e R s, d'ou es = s * et donc sts = s. Donc s est un inverse faible de t. La reciproque * est immediate. Si de plus (3) est vraie, s est inverse de t. *------------------------------------------------------------------- */ #include <stdlib.h> #include <stdio.h> #include "Main.h" #include "Calcul.h" #include "DclassesIteratif.h" #include "Globales.h" #include "Memoire.h" #include "Reduction.h" #include "Sortie.h" #include "SortieLaTeX.h" #include "TableDeS.h" #include "Utilitaires.h" #include "Varietes.h" #include "Inverses.h" extern unsigned long NbElements, NbIdempotents; extern unsigned short NbLettres, PossedeUnNeutre; extern unsigned long TestsEffectues, Varietes, CalculsEffectues; extern char **Messages; extern info *Table; /* La table contenant les informations sur les elements */ extern info2 *Table2; /* La table contenant les autres informations sur les elements */ extern unsigned long *TableIdempotents; /* La table des idempotents */ extern unsigned long **TableDeS; /* La table de multiplication du semigroupe */ struct NumeroEtLettre *PileInverses; ListeNumero *Inverses, *InversesFaibles; static unsigned long NbGenerateursKS, TailleCourante; static unsigned long *TableKS, *TableGenerateursKS; /*************************************************************************** * * MiseAJour * ***************************************************************************/ void MiseAJour(unsigned long s, unsigned long t) { unsigned long st; ListeNumero Temporaire; st = ProduitParReduction(s, t); if ((Table[st].Statut & IDEMPOTENT) && (Table2[st].Rclasse == Table2[s].Rclasse)) /* s inverse faible de t */ { Temporaire = AlloueMemoireWagonNumero(); Temporaire->t = s; if ((Table2[s].Dclasse == Table2[t].Dclasse)) /* s inverse de t */ { Temporaire->suivant = Inverses[t]; Inverses[t] = Temporaire; } else /* s inverse faible de t */ { Temporaire->suivant = InversesFaibles[t]; InversesFaibles[t] = Temporaire; } } } /*************************************************************************** * * ParcoursGrapheJ. Parcours en profondeur du graphe de l'ordre <=J * a partir d'un sommet t. * ***************************************************************************/ void ParcoursGrapheJ(unsigned long t) { register lettre a; register long i; register unsigned long s, u; for (i = IDENTITE; i <= NbElements; i++) Table2[i].Statut &= ~D_VISITE; /* Initialisation des drapeaux */ i = 0; PileInverses[0].Numero = t; do { s = PileInverses[i].Numero; a = PileInverses[i].Lettre; if ((Table2[s].Statut & D_VISITE) == 0) /* Premiere visite dans s */ { MiseAJour(s, t); Table2[s].Statut |= D_VISITE; } u = (a < NbLettres) ? Table[s].Produits[a].D & ~EST_REDUIT : Table[s].Produits[a - NbLettres].G; if ((Table2[u].Statut & D_VISITE) == 0) /* Si possible, on descend en profondeur. */ PileInverses[++i].Numero = u; else if (a < (2 * NbLettres - 1)) /* Sinon, on explore les autres branches */ PileInverses[i].Lettre++; else /* Plus rien a explorer a ce niveau : on remonte */ PileInverses[i--].Lettre = 0; } while (i != -1); } /*************************************************************************** * * Inverses. * ***************************************************************************/ void CalculInverses(void) { unsigned long t; ListeNumero Temporaire; if (!(CalculsEffectues & CALCUL_INVERSES)) { CalculIdempotents(); CalculDclasses(); Inverses = AlloueMemoireTableListeNumero(); InversesFaibles = AlloueMemoireTableListeNumero(); if (NbLettres == 0) /* Cas du monoide trivial */ { Temporaire = AlloueMemoireWagonNumero(); Temporaire->t = IDENTITE; Temporaire->suivant = NULL; Inverses[IDENTITE] = Temporaire; return; } PileInverses = AlloueMemoirePileNumeroEtLettre(); for (t = IDENTITE; t <= NbElements; t++) ParcoursGrapheJ(t); CalculsEffectues |= CALCUL_INVERSES; /* On prend note : le calcul des inverses est termine */ } } /*************************************************************************** * * ProduitsDroits. Prend en argument un element u et calcule les elements ut et tu * ou t parcourt l'ensemble des generateurs de K(S). * ***************************************************************************/ void ProduitsDroits(unsigned long u) { unsigned long i, t, ut; for (i = 0; i < NbGenerateursKS; i++) /* Calcul de ut et de tu */ { t = TableGenerateursKS[i]; ut = TableDeS[u][t]; if ((Table[ut].Statut & EST_DANS_KS) == 0) /* Si ut n'est pas deja dans K(S) */ { TableKS[TailleCourante++] = ut; Table[ut].Statut |= EST_DANS_KS; } } } /*************************************************************************** * * ProduitsGauches. Prend en argument un element u et calcule les elements tu * ou t parcourt les K premiers de generateurs de K(S). * ***************************************************************************/ void ProduitsGauches(unsigned long u) { unsigned long i, t, tu; for (i = 0; i < NbGenerateursKS; i++) /* Calcul de tu */ { t = TableGenerateursKS[i]; tu = TableDeS[t][u]; if ((Table[tu].Statut & EST_DANS_KS) == 0) /* Si tu n'est pas deja dans K(S) */ { TableKS[TailleCourante++] = tu; Table[tu].Statut |= EST_DANS_KS; } } } /*************************************************************************** * * Conjugue. Prend en argument des elements u et s et calcule les elements * de la forme v = sut, ou t est un inverse de s. Pour chaque element v ainsi * trouve, on calcule les produits * ***************************************************************************/ void Conjugue(unsigned long i, unsigned long s) { unsigned long j, t, sut, u, v; ListeNumero Liste; u = TableKS[i]; Liste = Inverses[s]; while (Liste != NULL) { t = Liste->t; sut = TableDeS[TableDeS[s][u]][t]; if ((Table[sut].Statut & EST_DANS_KS) == 0) /* Si sut n'est pas dans K(S) */ { TableKS[TailleCourante++] = TableGenerateursKS[NbGenerateursKS++] = sut; Table[sut].Statut |= EST_DANS_KS; for (j = 0; j < i; j++) { v = TableKS[j]; ProduitsGauches(v); } } Liste = Liste->suivant; } } /*************************************************************************** * * ConjugueFaiblement. Prend en argument des elements u et s et calcule les * elements de la forme sut et tus, ou t est un inverse faible de s. * ***************************************************************************/ void ConjugueFaiblement(unsigned long i, unsigned long s) { unsigned long j, t, sut, tus, u, v; ListeNumero Liste; u = TableKS[i]; Liste = InversesFaibles[s]; while (Liste != NULL) { t = Liste->t; sut = TableDeS[TableDeS[s][u]][t]; if ((Table[sut].Statut & EST_DANS_KS) == 0) /* Si sut n'est pas dans K(S) */ { TableKS[TailleCourante++] = TableGenerateursKS[NbGenerateursKS++] = sut; Table[sut].Statut |= EST_DANS_KS; for (j = 0; j < i; j++) { v = TableKS[j]; ProduitsGauches(v); } } tus = TableDeS[TableDeS[t][u]][s]; if ((Table[tus].Statut & EST_DANS_KS) == 0) /* Si tus n'est pas dans K(S) */ { TableKS[TailleCourante++] = TableGenerateursKS[NbGenerateursKS++] = tus; Table[tus].Statut |= EST_DANS_KS; for (j = 0; j < i; j++) { v = TableKS[j]; ProduitsGauches(v); } } Liste = Liste->suivant; } } /*************************************************************************** * * Calcul du noyau. * K(S) est l'intersection des \tau^{-1}(1), prise sur tous les morphismes * relationnels \tau de M dans un groupe G. D'apres le theoreme de Ash, on a * K(S) = D(S), ou D(S) est le plus petit sous-semigroupe de S ferme par * conjugaison faible. Comme D(S) contient E(S), on part de E(S) et on fait * for each u in D(S) * for each weakly conjugate pair (s, t) * add sut and tus to D(S) * add D(S)u to D(S) * Si les idempotents commutent, K(S) = E(S) * ***************************************************************************/ void CalculKS(void) { unsigned long i, s; if (!(CalculsEffectues & CALCUL_KS)) { TestECom(); if (Varietes & SEM_ECOM) /* Le semigroupe est dans Ecom, K(S) = E(S) */ { for (i = 0; i < NbIdempotents; i++) Table[TableIdempotents[i]].Statut |= EST_DANS_KS; return; } CalculListeIdempotents(); /* Calculs preliminaires */ CalculInverses(); CalculTableDeS(); TableKS = AlloueMemoireTableau(NbElements); TableGenerateursKS = AlloueMemoireTableau(NbElements); for (i = 0; i < NbIdempotents; i++) /* Au depart, K(S) = E(S) */ { TableKS[i] = TableGenerateursKS[i] = TableIdempotents[i]; Table[TableIdempotents[i]].Statut |= EST_DANS_KS; } NbGenerateursKS = TailleCourante = NbIdempotents; i = 0; while (i < TailleCourante) { for (s = IDENTITE + !PossedeUnNeutre; s <= NbElements; s++) /* Calcul de sut */ { Conjugue(i, s); ConjugueFaiblement(i, s); } ProduitsDroits(TableKS[i]); i++; } free(TableKS); free(TableGenerateursKS); CalculsEffectues |= CALCUL_KS; /* On prend note : le calcul de K(S) est termine */ } }