/***************************************
* *
* 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;
}
}