/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * Varietes.c Jean-Eric Pin 07/12/96 * Modifications pour B1 le 11/03/97 *------------------------------------------------------------------- */ #include <stdlib.h> #include <stdio.h> #include "Main.h" #include "Calcul.h" #include "DclassesIteratif.h" #include "Initialisation.h" #include "TableDeS.h" #include "Reduction.h" #include "Syntactique.h" #include "Varietes.h" #include "Zero.h" extern element *Generateurs; extern info *Table; extern info2 *Table2; extern unsigned short NbLettres, PossedeUnNeutre, PossedeUnZero; extern unsigned long TestsEffectues, Varietes, CalculsEffectues; extern unsigned long DernierMot, NbElements, NbIdempotents, NbRclasses, NbLclasses, NbDclasses; extern unsigned long *TableIdempotents; /* La table des idempotents */ extern infoSommet **Graphe; /* Le graphe syntactique */ extern ProduitRapide_ ProduitRapide; adresses Adresses; /************************************************************ * * TestCommutatif. * Retourne 1 si S est commutatif et 0 sinon. * Dans ce dernier cas, trouve un couple (u, v) tel que uv != vu. * ************************************************************/ void TestCommutatif(void) { lettre a, b; unsigned long na, nb; if (!(TestsEffectues & SEM_COMMUTATIF)) { TestsEffectues |= SEM_COMMUTATIF; /* On prend note : la variete Com a ete testee. */ for (a = 0; a < NbLettres; a++) { na = Table[IDENTITE].Produits[a].D; for (b = 0; b < NbLettres; b++) { nb = Table[IDENTITE].Produits[b].D; if (ProduitRapide(na, nb) != ProduitRapide(nb, na)) { *Adresses.commutatif_1 = a; *Adresses.commutatif_2 = b; return; } } } Varietes |= SEM_COMMUTATIF; } } /************************************************************ * * TestIdempotent. * Retourne 1 si S est idempotent et 0 sinon. * Dans ce dernier cas, trouve un element u tel que uu != u. * ************************************************************/ void TestIdempotent(void) { unsigned long u; if (!(TestsEffectues & SEM_IDEMPOTENT)) { TestsEffectues |= SEM_IDEMPOTENT; /* On prend note : la variete A_1 a ete testee. */ if (NbElements <= 1) /* Cas du semigroupe trivial */ { Varietes |= SEM_IDEMPOTENT; return; } else CalculxOmega(); for (u = IDENTITE + 1; u != 0; u = Table[u].Suivant) if (Table2[u].xOmega != u) { *Adresses.idempotent = u; return; } Varietes |= SEM_IDEMPOTENT; } } /************************************************************ * * TestNilpotent. * Retourne 1 si S est nilpotent et 0 sinon. * ************************************************************/ void TestNilpotent(void) { if (!(TestsEffectues & SEM_NILPOTENT)) { TesteZero(); CalculIdempotents(); if ((PossedeUnZero) && (NbIdempotents == 1)) Varietes |= SEM_NILPOTENT; TestsEffectues |= SEM_NILPOTENT; /* On prend note : la variete Nil a ete testee. */ } } /************************************************************ * * TestAperiodique. * Retourne 1 si S est aperiodique et 0 sinon. * Dans ce dernier cas, trouve un element u tel que u^u != u^. * ************************************************************/ void TestAperiodique(void) { unsigned long u, uOmega; if (!(TestsEffectues & SEM_APERIODIQUE)) { TestsEffectues |= SEM_APERIODIQUE; /* On prend note : la variete A a ete testee. */ if (NbElements <= 1) /* Cas du semigroupe trivial */ { Varietes |= SEM_APERIODIQUE; return; } else CalculxOmega(); for (u = IDENTITE + !PossedeUnNeutre; u != 0; u = Table[u].Suivant) { uOmega = Table2[u].xOmega; if (ProduitRapide(uOmega, u) != uOmega) { *Adresses.aperiodique = u; return; } } Varietes |= SEM_APERIODIQUE; } } /************************************************************ * * TestUnGroupe. * Retourne 1 si S est un groupe et 0 sinon. * ************************************************************/ void TestUnGroupe(void) { if (!(TestsEffectues & SEM_GROUPE)) { TestsEffectues |= SEM_GROUPE; /* On prend note : la variete G a ete testee. */ CalculIdempotents(); if ((CalculsEffectues & CALCUL_D_CLASSES) == 0) CalculDclasses(); if ((NbIdempotents == 1) && (NbDclasses == 1)) Varietes |= SEM_GROUPE; } } /************************************************************ * * TestRtrivial. * Retourne 1 si S est R-trivial et 0 sinon. * ************************************************************/ void TestRtrivial(void) { if (!(TestsEffectues & SEM_R_TRIVIAL)) { TestsEffectues |= SEM_R_TRIVIAL; /* On prend note : la variete R a ete testee. */ if ((CalculsEffectues & CALCUL_R_CLASSES) == 0) CalculRclassesIteratif(); if (NbElements == NbRclasses) Varietes |= SEM_R_TRIVIAL; } } /************************************************************ * * TestLtrivial. * Retourne 1 si S est L-trivial et 0 sinon. * ************************************************************/ void TestLtrivial(void) { if (!(TestsEffectues & SEM_L_TRIVIAL)) { TestsEffectues |= SEM_L_TRIVIAL; /* On prend note : la variete L a ete testee. */ if ((CalculsEffectues & CALCUL_D_CLASSES) == 0) CalculDclasses(); if (NbElements == NbLclasses) Varietes |= SEM_L_TRIVIAL; } } /************************************************************ * * TestDtrivial. * Retourne 1 si S est D-trivial et 0 sinon. * ************************************************************/ void TestDtrivial(void) { if (!(TestsEffectues & SEM_D_TRIVIAL)) { TestsEffectues |= SEM_D_TRIVIAL; /* On prend note : la variete J a ete testee. */ if ((CalculsEffectues & CALCUL_D_CLASSES) == 0) CalculDclasses(); if (NbElements == NbDclasses) Varietes |= SEM_D_TRIVIAL; } } /************************************************************ * * TestDA. * Retourne 1 si S est dans DA et 0 sinon. Dans ce dernier cas, * trouve (x, y) tels que (xy)^(yx)^(xy)^ != (xy)^. * Algorithme a ameliorer !! * ************************************************************/ void TestDA(void) { unsigned long e, f, efe, x, y; if (!(TestsEffectues & SEM_DA)) { TestsEffectues |= SEM_DA; /* On prend note : la variete DA a ete testee. */ TestAperiodique(); if (!(Varietes & SEM_APERIODIQUE)) /* Ce semigroupe n'est pas aperiodique */ return; CalculxOmega(); for (x = IDENTITE + !PossedeUnNeutre; x != 0; x = Table[x].Suivant) for (y = IDENTITE + !PossedeUnNeutre; y != 0; y = Table[y].Suivant) { e = Table2[ProduitRapide(x, y)].xOmega; f = Table2[ProduitRapide(y, x)].xOmega; efe = ProduitRapide(ProduitRapide(e, f), e); if (efe != e) { *Adresses.DA_x = x; *Adresses.DA_y = y; return; } } Varietes |= SEM_DA; } } /************************************************************ * * TestDS. * Retourne 1 si S est dans DS et 0 sinon. Dans ce dernier cas, * trouve (x, y) tels que ((xy)^(yx)^(xy)^)^ != (xy)^. * Algorithme a ameliorer !! * ************************************************************/ void TestDS(void) { unsigned long e, f, efe, efew, x, y; if (!(TestsEffectues & SEM_DS)) { TestsEffectues |= SEM_DS; /* On prend note : la variete DS a ete testee. */ CalculxOmega(); for (x = IDENTITE + !PossedeUnNeutre; x != 0; x = Table[x].Suivant) for (y = IDENTITE + !PossedeUnNeutre; y != 0; y = Table[y].Suivant) { e = Table2[ProduitRapide(x, y)].xOmega; f = Table2[ProduitRapide(y, x)].xOmega; efe = ProduitRapide(ProduitRapide(e, f), e); efew = Table2[efe].xOmega; if (efew != e) { *Adresses.DS_x = x; *Adresses.DS_y = y; return; } } Varietes |= SEM_DS; } } /************************************************************ * * TestRvL. * Retourne 1 si S est dans R v L et 0 sinon. Dans ce dernier cas, * trouve (x, y, z) tels que (xy)^x(zx)^ != (xy)^(zx)^. * ************************************************************/ void TestRvL(void) { unsigned long e, f, x, y, z; if (!(TestsEffectues & SEM_RvL)) { TestsEffectues |= SEM_RvL; /* On prend note : la variete R v L a ete testee. */ CalculxOmega(); for (x = IDENTITE + !PossedeUnNeutre; x != 0; x = Table[x].Suivant) for (y = IDENTITE + !PossedeUnNeutre; y != 0; y = Table[y].Suivant) for (z = IDENTITE + !PossedeUnNeutre; z != 0; z = Table[z].Suivant) { e = Table2[ProduitRapide(x, y)].xOmega; /* (xy)^ */ f = Table2[ProduitRapide(z, x)].xOmega; /* (zx)^ */ if (ProduitRapide(ProduitRapide(e, x), f) != ProduitRapide(e, f)) { *Adresses.RvL_x = x; *Adresses.RvL_y = y; *Adresses.RvL_z = z; return; } } Varietes |= SEM_RvL; } } /************************************************************ * * TestL1. * Retourne 1 si S est localement trivial. * Sinon, trouve des elements x et u tel que x^ux^ != x^. * ************************************************************/ void TestL1(void) { unsigned long i, e, s, ese; if (!(TestsEffectues & SEM_LI)) { TestsEffectues |= SEM_LI; /* On prend note : la variete LI a ete testee. */ CalculListeIdempotents(); for (i = 0; i < NbIdempotents; i++) { e = TableIdempotents[i]; for (s = IDENTITE + !PossedeUnNeutre; s <= NbElements; s++) { ese = ProduitRapide(e, ProduitRapide(s, e)); if (ese != e) { *Adresses.L1_e = e; *Adresses.L1_s = s; return; } } } Varietes |= SEM_LI; } } /************************************************************ * * TestLG. * Retourne 1 si S est localement un groupe. * Sinon, trouve des elements x et u tel que (x^ux^)^ != x^. * ************************************************************/ void TestLG(void) { unsigned long i, e, s, ese_omega; if (!(TestsEffectues & SEM_LG)) { TestsEffectues |= SEM_LG; /* On prend note : la variete LG a ete testee. */ CalculListeIdempotents(); for (i = 0; i < NbIdempotents; i++) { e = TableIdempotents[i]; for (s = IDENTITE + !PossedeUnNeutre; s <= NbElements; s++) { ese_omega = Table2[ProduitRapide(e, ProduitRapide(s, e))].xOmega; if (ese_omega != e) { *Adresses.LG_e = e; *Adresses.LG_s = s; return; } } } Varietes |= SEM_LG; } } /************************************************************************** * * TestConjecture. * **************************************************************************/ void TestConjecture(void) { unsigned long i, j, e, f, p, q, r, s, epf, qe, er, fse, epfqeOmega, erfseOmega; if (!(TestsEffectues & SEM_B_UN)) { TestsEffectues |= SEM_B_UN; /* On prend note : la variete B_1 a ete testee. */ CalculTableDeS(); CalculListeIdempotents(); CalculxOmega(); for (i = 0; i < NbIdempotents; i++) { e = TableIdempotents[i]; for (q = IDENTITE + !PossedeUnNeutre; q != 0; q = Table[q].Suivant) { qe = ProduitRapide(q, e); for (r = IDENTITE + !PossedeUnNeutre; r != 0; r = Table[r].Suivant) { er = ProduitRapide(e, r); for (j = 0; j < NbIdempotents; j++) { f = TableIdempotents[j]; for (p = IDENTITE + !PossedeUnNeutre; p != 0; p = Table[p].Suivant) { epf = ProduitRapide(ProduitRapide(e, p), f); epfqeOmega = Table2[ProduitRapide(epf, qe)].xOmega; for (s = IDENTITE + !PossedeUnNeutre; s != 0; s = Table[s].Suivant) { fse = ProduitRapide(ProduitRapide(f, s), e); erfseOmega = Table2[ProduitRapide(er, fse)].xOmega; if (ProduitRapide(ProduitRapide(epfqeOmega, epf),ProduitRapide(fse, erfseOmega)) != ProduitRapide(epfqeOmega, erfseOmega)) { *Adresses.B1_p = p; *Adresses.B1_q = q; *Adresses.B1_r = r; *Adresses.B1_s = s; *Adresses.B1_e = e; *Adresses.B1_f = f; return; } } } } } } } Varietes |= SEM_B_UN; } } /************************************************************************** * * TestB1Plus. * Retourne 1 si (S, <= ) verifie l'identite ese <= e et 0 sinon. Dans ce dernier cas, * trouve (e, s) tels que ese ne soit pas inferieur ou egal a e. * **************************************************************************/ void TestB1Plus(void) { unsigned long i, e, s, ese; if (!(TestsEffectues & SEM_B_UN_PLUS)) { TestsEffectues |= SEM_B_UN_PLUS; /* On prend note : la variete B_1 a ete testee. */ CalculListeIdempotents(); for (i = 0; i < NbIdempotents; i++) { e = TableIdempotents[i]; for (s = IDENTITE + !PossedeUnNeutre; s <= NbElements; s++) { ese = ProduitRapide(e, ProduitRapide(s, e)); if ((Graphe[ese][e].Label & CHAR_DEUX) == 0) { *Adresses.B1Plus_e = e; *Adresses.B1Plus_s = s; return; } } } Varietes |= SEM_B_UN_PLUS; } } /************************************************************************** * * TestECom. * Retourne 1 si les idempotents de S commutent et 0 sinon. Dans ce dernier cas, * trouve (e, f) tels que ef != fe. * **************************************************************************/ void TestECom(void) { unsigned long i, j, e, f; if (!(TestsEffectues & SEM_ECOM)) { TestsEffectues |= SEM_ECOM; /* On prend note : la variete Ecom a ete testee. */ CalculListeIdempotents(); for (i = 0; i < NbIdempotents; i++) for (j = 0; j < NbIdempotents; j++) { e = TableIdempotents[i]; f = TableIdempotents[j]; if (ProduitRapide(e, f) != ProduitRapide(f, e)) { *Adresses.ECom_e = e; *Adresses.ECom_f = f; return; } } Varietes |= SEM_ECOM; } } /************************************************************************** * * TestBG. * Retourne 1 si S est bloc-groupe et 0 sinon. Dans ce dernier cas, * trouve (e, f) tels que e^f^ != f^e^. * **************************************************************************/ void TestBG(void) { unsigned long e, f, i, j; if (!(TestsEffectues & SEM_BG)) { TestsEffectues |= SEM_BG; /* On prend note : la variete BG a ete testee. */ CalculListeIdempotents(); CalculxOmega(); for (i = 0; i < NbIdempotents; i++) for (j = 0; j < NbIdempotents; j++) { e = TableIdempotents[i]; f = TableIdempotents[j]; if (Table2[ProduitRapide(e, f)].xOmega != Table2[ProduitRapide(f, e)].xOmega) { *Adresses.BG_e = e; *Adresses.BG_f = f; return; } } Varietes |= SEM_BG; } } /************************************************************************** * * TestConjecture * **************************************************************************/ void TestB1(void) { unsigned long i, j, e, f, p, q, r, s, ep, fq, pf, qe, qf, er, epf, fse, epfqeOmega, erfseOmega; /* eq, fp, */ if (!(TestsEffectues & SEM_B_UN)) { TestsEffectues |= SEM_B_UN; /* On prend note : la variete B_1 a ete testee. */ CalculTableDeS(); CalculListeIdempotents(); CalculxOmega(); CalculDclasses(); for (i = 0; i < NbIdempotents; i++) { e = TableIdempotents[i]; for (q = IDENTITE + !PossedeUnNeutre; q != 0; q = Table[q].Suivant) { /* * if (Table2[q].Rclasse != Table2[Table2[q].xOmega].Rclasse) * continue; */ for (r = IDENTITE + !PossedeUnNeutre; r != 0; r = Table[r].Suivant) { er = ProduitRapide(e, r); for (j = 0; j < NbIdempotents; j++) { f = TableIdempotents[j]; qf = ProduitRapide(q, f); /* * if (Table2[qf].Rclasse != Table2[f].Rclasse) * continue; */ qe = ProduitRapide(q, e); /* * if (Table2[qe].Rclasse != Table2[q].Rclasse) * continue; */ /* * eq = ProduitRapide(e, q); * if (Table2[eq].Rclasse != Table2[e].Rclasse) * continue; */ fq = ProduitRapide(q, f); /* * if (Table2[fq].Rclasse != Table2[q].Rclasse) * continue; */ for (p = IDENTITE + !PossedeUnNeutre; p != 0; p = Table[p].Suivant) { /* * if (Table2[p].Rclasse != Table2[Table2[p].xOmega].Rclasse) * continue; * if (Table2[p].Rclasse != Table2[r].Rclasse) * continue; */ /* * fp = ProduitRapide(f, p); * if (Table2[fp].Rclasse != Table2[f].Rclasse) * continue; */ ep = ProduitRapide(e, p); /* * if (Table2[ep].Rclasse != Table2[p].Rclasse) * continue; * pe = ProduitRapide(p, e); * if (Table2[pe].Rclasse != Table2[e].Rclasse) * continue; */ pf = ProduitRapide(p, f); /* * if (Table2[pf].Rclasse != Table2[p].Rclasse) * continue; */ epf = ProduitRapide(ep, f); epfqeOmega = Table2[ProduitRapide(epf, qe)].xOmega; for (s = IDENTITE + !PossedeUnNeutre; s != 0; s = Table[s].Suivant) { /* * if (Table2[q].Rclasse != Table2[s].Rclasse) * continue; */ fse = ProduitRapide(ProduitRapide(f, s), e); erfseOmega = Table2[ProduitRapide(er, fse)].xOmega; if (ProduitRapide(ProduitRapide(epfqeOmega, epf), ProduitRapide(fse, erfseOmega)) != ProduitRapide(epfqeOmega, erfseOmega)) { *Adresses.B1_p = p; *Adresses.B1_q = q; *Adresses.B1_r = r; *Adresses.B1_s = s; *Adresses.B1_e = e; *Adresses.B1_f = f; return; } } } } } } } Varietes |= SEM_B_UN; } }