/***************************************
*                                      *
*   Copyright (c) 1998 Jean-Eric Pin   *
*   All rights reserved.               *
*                                      *
*   TAB = 2 spaces                     *
*                                      *
***************************************/

/*-------------------------------------------------------------------
 * Exemples.c    Jean-Eric Pin 07/12/96
 *-------------------------------------------------------------------
 */     

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include "Main.h"
#include "Arithmetique.h"
#include "Exemples.h"
#include "Initialisation.h"
#include "Matrices.h"
#include "MatricesBooleennes.h"
#include "MatricesMaxPlus.h"
#include "Memoire.h"
#include "Transitions.h"

extern unsigned short NbEtats, NbLettres, TypeSemigroupe, TypeCalcul;
extern unsigned long Periode, Seuil;
extern element *Generateurs;
extern element *TableDesValeurs;
extern numero TailleMaxi;
extern unsigned long TailleTableDeHachage;
extern char *EtatsFinaux;
extern Hachage_ Hachage;
extern Hachage_ HachageSecondaire;


/****************************************************
*
* Le semigroupe aperiodique de Brandt. OK
*
*****************************************************/

void BAn(unsigned short n)
{
  short q;
  lettre a;

  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Semigroupe;
  NbEtats = n;
  NbLettres = n;
  Choix();
  AlloueMemoireGenerateurs();

  for (a = 0; a < NbLettres; a++)
    for (q = 0; q <= NbEtats; q++)
      ((Transitions)Generateurs[a])[q] = 0;
  for (a = 0; a < NbLettres - 1; a++)
    ((Transitions)Generateurs[a])[a + 1] = a + 2;
  ((Transitions)Generateurs[NbLettres - 1])[n] = 1;
  
  TailleMaxi = n * n + 2;
}

/****************************************************************************
*
* Le semigroupe relativement libre de la variete engendree par BA_2. OK
*
*****************************************************************************/

void FBAn(unsigned short n)
{
  short i, q;
  lettre a;

  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Semigroupe;
  q = 1;
  for (i = 0; i < n; i++, q *= 5)
    ;          /* On obtient 5^n */
  NbEtats = q * 2;
  NbLettres = 2;
  Choix();
  AlloueMemoireGenerateurs();

  for (a = 0; a < NbLettres; a++)
    for (q = 0; q <= NbEtats; q++)
      ((Transitions)Generateurs[a])[q] = 0;
  for (a = 0; a < NbLettres - 1; a++)
    ((Transitions)Generateurs[a])[a + 1] = a + 2;
  ((Transitions)Generateurs[NbLettres - 1])[n] = 1;
  
  TailleMaxi = n * n + 2;
}

/****************************************************
*
* Le monoide aperiodique de Brandt. OK
*
*****************************************************/

void MBAn(unsigned short n)
{
  BAn(n);
  TypeCalcul = Monoide;
}

/*********************************************************************
*
* Le monoide syntactique de (a(a(a...a(ab)*)b)* ... b)*)b)*)b)*  (nfois)
*
**********************************************************************/

void CompteurSeuil(unsigned short n)
{
  short q;

  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 2;
  Choix();
  AlloueMemoireGenerateurs();

  for (q = 1; q < NbEtats; q++)
  {
    ((Transitions)Generateurs[0])[q] = q + 1;
    ((Transitions)Generateurs[1])[q] = q - 1;
  }
  ((Transitions)Generateurs[0])[n] = 0;
  ((Transitions)Generateurs[1])[n] = n-1;
  
  TailleMaxi = (long)(1 + (n * (n + 1) * (2 * n + 1) / 6));
}

/**************************************************
*
* Multiplication par n (Etats 0, ..., n-1)
*
**************************************************/
/*************************************************
 *           | q * 0 | q * 1 |   q.0   |   q.1   |
 *************************************************
 * q pair    |   0   |   1   |   q/2   | n+q-1/2 |
 * q impair  |   1   |   0   | (q-1)/2 |  n+q/2  |
 *************************************************/

void Multiplication(unsigned short n)
{
  short k = 0, q;

  while (n % 2 == 0)
  {
    k++;
    n /= 2;
  }
  TypeSemigroupe = ParTransitions;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 2;
  Choix();
  AlloueMemoireGenerateurs();
  q = k = 1;
  while (k <= NbEtats/2)
  {
    ((Transitions)Generateurs[0])[q++] = k;
    ((Transitions)Generateurs[0])[q++] = k++;
  }  
  ((Transitions)Generateurs[0])[q] = k;
  q = 1;
  ((Transitions)Generateurs[1])[q++] = k;
  while (k < NbEtats)
  {
    ((Transitions)Generateurs[1])[q++] = ++k;
    ((Transitions)Generateurs[1])[q++] = k;
  }  
  TailleMaxi = n * n;
}

/****************************************************
*
* Le groupe symetrique. OK
*
*
* Les 2 generateurs sont
* (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)
* (2 3 4.. . n   1)    (2 1 3 ... n-1 n)
*
* L'ordre du groupe est n!
*
*****************************************************/

void Sn(unsigned short n)
{
  short q;
  
  TypeSemigroupe = ParTransitions;
  TypeCalcul = Monoide;
  NbLettres = 2;
  NbEtats = n;
  Choix();
  
  if (NbEtats > 2)
  {
    AlloueMemoireGenerateurs();
    for (q = 1; q < NbEtats; q++)
      ((Transitions)Generateurs[0])[q] = q+1;
    ((Transitions)Generateurs[0])[NbEtats] = 1;
  
    for (q = 3; q <= NbEtats; q++)
      ((Transitions)Generateurs[1])[q] = q;
    ((Transitions)Generateurs[1])[1] = 2;
    ((Transitions)Generateurs[1])[2] = 1;
  }
  else if (NbEtats == 2)
  {
    NbLettres = 1;
    Hachage = HachageUneLettreTransitions;
    HachageSecondaire = HachageSecondaireUneLettreTransitions;
    AlloueMemoireGenerateurs();
    ((Transitions)Generateurs[0])[1] = 2;
    ((Transitions)Generateurs[0])[2] = 1;
  }
  else if (NbEtats == 1)
  {
    NbLettres = 0;
    Hachage = HachageUneLettreTransitions;
    HachageSecondaire = HachageSecondaireUneLettreTransitions;
    AlloueMemoireGenerateurs();
    ((Transitions)Generateurs[0])[1] = 1;
  }
  TailleMaxi = 1;
  for (q = 2; q <= n; TailleMaxi = TailleMaxi * q++)
    ;  /* n! */
}

/****************************************************************
*
* Le semigroupe de toutes les transformations. OK
*
* Les 3 generateurs sont
* (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)
* (2 3 4.. . n   1)    (2 1 3 ... n-1 n)    (1 2 3 ... n-1 1)
*
* L'ordre du monoide est n^n.
*
******************************************************************/

 void Tn(unsigned short n)
{
  short q;
  
  TypeSemigroupe = ParTransitions;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 3;
  Choix();
  
  if (NbEtats > 2)
  {
    AlloueMemoireGenerateurs();
    for (q = 1; q < NbEtats; q++)
    {
      ((Transitions)Generateurs[0])[q] = q+1;
      ((Transitions)Generateurs[2])[q] = q;
    }
    ((Transitions)Generateurs[0])[NbEtats] = 1;
    ((Transitions)Generateurs[2])[NbEtats] = 1;
    for (q = 3; q <= NbEtats; q++)
      ((Transitions)Generateurs[1])[q] = q;
    ((Transitions)Generateurs[1])[1] = 2;
    ((Transitions)Generateurs[1])[2] = 1;
  }
  else if (NbEtats == 2)
  {
    NbLettres = 2;
    AlloueMemoireGenerateurs();
    ((Transitions)Generateurs[0])[1] = 2;
    ((Transitions)Generateurs[0])[2] = 1;
    ((Transitions)Generateurs[1])[1] = 1;
    ((Transitions)Generateurs[1])[2] = 1;
  }
  else if (NbEtats == 1)
  {
    NbLettres = 1;
    Hachage = HachageUneLettreTransitions;
    HachageSecondaire = HachageSecondaireUneLettreTransitions;
    AlloueMemoireGenerateurs();
    ((Transitions)Generateurs[0])[1] = 1;
  }
  TailleMaxi = (unsigned long)ceil(pow(n,n));
/*  AlloueMemoireFinaux(); 
  EtatsFinaux[1] = 1;  
  EtatsFinaux[2] = 1;  
  EtatsFinaux[3] = 1;  */
}

/******************************************************************************
*
* Le semigroupe de toutes les fonctions. OK
*
* Les 4 generateurs sont
* (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)
* (2 3 4.. . n   1)    (2 1 3 ... n-1 n)    (1 2 3 ... n-1 1)    (1 2 3 ... n-1 -)
*
* L'ordre du monoide est (n+1)^n.
*
*******************************************************************************/

void Fn(unsigned short n)
{
  short q;
  
  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 4;
  Choix();
  
  if (NbEtats > 2)
  {
    AlloueMemoireGenerateurs();
    for (q = 1; q < NbEtats; q++)
    {
      ((Transitions)Generateurs[0])[q] = q+1;
      ((Transitions)Generateurs[2])[q] = q;
      ((Transitions)Generateurs[3])[q] = q;
    }
    ((Transitions)Generateurs[0])[NbEtats] = 1;
    ((Transitions)Generateurs[2])[NbEtats] = 1;
    ((Transitions)Generateurs[3])[NbEtats] = 0;
    for (q = 3; q <= NbEtats; q++)
      ((Transitions)Generateurs[1])[q] = q;
    ((Transitions)Generateurs[1])[1] = 2;
    ((Transitions)Generateurs[1])[2] = 1;
  }
  else if (NbEtats == 2)
  {
    NbLettres = 3;
    AlloueMemoireGenerateurs();
    ((Transitions)Generateurs[0])[1] = 2;
    ((Transitions)Generateurs[0])[2] = 1;
    ((Transitions)Generateurs[1])[1] = 1;
    ((Transitions)Generateurs[1])[2] = 1;
    ((Transitions)Generateurs[2])[1] = 1;
    ((Transitions)Generateurs[2])[2] = 0;
  }
  else if (NbEtats == 1)
  {
    NbLettres = 2;
    AlloueMemoireGenerateurs();
    ((Transitions)Generateurs[0])[1] = 1;
    ((Transitions)Generateurs[1])[1] = 0;
  }
  TailleMaxi = (unsigned long)ceil(pow(n + 1, n));
}

/******************************************************************************
*
* Le semigroupe des fonctions injectives. OK
*
* Les 3 generateurs sont
* (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)
* (2 3 4.. . n   1)    (2 1 3 ... n-1 n)    (1 2 3 ... n-1 -)
*
* L'ordre du monoide est .
*
*******************************************************************************/

void In(unsigned short n)
{
  short q;
  
  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 3;
  Choix();
  AlloueMemoireGenerateurs();
  
  if (NbEtats > 2)
  {
    for (q = 1; q < NbEtats; q++)
    {
      ((Transitions)Generateurs[0])[q] = q+1;
      ((Transitions)Generateurs[2])[q] = q;
    }
    ((Transitions)Generateurs[0])[NbEtats] = 1;
    ((Transitions)Generateurs[2])[NbEtats] = 0;
    for (q = 3; q <= NbEtats; q++)
      ((Transitions)Generateurs[1])[q] = q;
    ((Transitions)Generateurs[1])[1] = 2;
    ((Transitions)Generateurs[1])[2] = 1;
  }
  else if (NbEtats == 2)
  {
    ((Transitions)Generateurs[0])[1] = 2;
    ((Transitions)Generateurs[0])[2] = 1;
    ((Transitions)Generateurs[1])[1] = 2;
    ((Transitions)Generateurs[1])[2] = 1;
    ((Transitions)Generateurs[2])[1] = 1;
    ((Transitions)Generateurs[2])[2] = 0;
  }
  else if (NbEtats == 1)
  {
    ((Transitions)Generateurs[0])[1] = 1;
    ((Transitions)Generateurs[1])[1] = 1;
    ((Transitions)Generateurs[2])[1] = 0;
  }
  TailleMaxi = (unsigned long)Stirling(n);
}

/****************************************************
*
* Fonctions qui preservent l'ordre. OK
*
* Les n generateurs. Pour 1 <= i <= n-1, a_i =
* (1 2 ... i-1  i  i+1 ... n)    
* (1 2 ... i-1 i+1 i+1 ... n)  
* et a_0 =
* (1 2 ... n-1  n )
* (1 1 ... n-2 n-1)
* L'ordre du monoide est Binomial(2n-1, n).
*
*****************************************************/

void On(unsigned short n)
{
  short q;
  lettre a;
  unsigned long T;
  
  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = n;
  Choix();
  AlloueMemoireGenerateurs();
  
  for (a = 1; a < NbLettres; a++)        /* a_i = (1 2 ... i-1 i+1 i+1 ... n) */
  {
    for (q = 1; q <= a-1; q++)
      ((Transitions)Generateurs[a])[q] = q;
    ((Transitions)Generateurs[a])[a] = a+1;
    for (q = a+1; q <= NbEtats; q++)
      ((Transitions)Generateurs[a])[q] = q;
  }
  a = 0;                    /* Le premier generateur : (1 1 ... n-2 n-1) */
  ((Transitions)Generateurs[a])[1] = 1;
  for (q = 2; q <= NbEtats; q++)
    ((Transitions)Generateurs[a])[q] = q - 1;    
  
  T = 1;
  for (q = 2; q <= NbEtats; q++)
  {
    T = 2 * (2 * q - 1) * T;
    T = ceil(T / q);
  }
  TailleMaxi = T;        /* Binomial(2n-1, n) */
}

/****************************************************
*
* Fonctions injectives qui preservent l'ordre. OK
*
* Les n generateurs sont, pour n = 4,
* (1 2 3 4)    (1 2 3 4)    (1 2 3 4)    (1 2 3 4)
* (1 2 4 -)    (1 3 - 4)    (2 - 3 4)    (- 1 2 3)
*
* L'ordre du monoide est Binomial(2n, n).
*
*****************************************************/

void POIn(unsigned short n)
{
  short q;
  lettre a;
  unsigned long T;
  
  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = n;
  Choix();
  AlloueMemoireGenerateurs();
  
  if (NbEtats > 1)
  {
    for (a = 0; a < NbLettres-1; a++)        /* a = (1 2 ... (n-a)-2 (n-a) 0 (n-a)+1 ... n) */
    {
      ((Transitions)Generateurs[a+1])[0] = 0;
      
      for (q = 1; q <= NbEtats; q++)
        ((Transitions)Generateurs[a+1])[q] = q;
        
      ((Transitions)Generateurs[a+1])[NbEtats - (a + 1)] = NbEtats - a;
      ((Transitions)Generateurs[a+1])[NbEtats - a] = 0;
    }
    a = 0;                    /* Le premier generateur : (0 1 2 3 ... n-1) */
    ((Transitions)Generateurs[a])[0] = 0;
    for (q = 2; q <= NbEtats; q++)
      ((Transitions)Generateurs[a])[q] = q - 1;    
  }
  else if (NbEtats == 1)
  {
    ((Transitions)Generateurs[0])[0] = 0;
    ((Transitions)Generateurs[0])[1] = 0;
  }
  
  T = 2;
  for (q = 2; q <= NbEtats; q++)
  {
    T = 2 * (2 * q - 1) * T;
    T = ceil(T / q);
  }
  TailleMaxi = T;        /* Binomial(2n, n) */
}

/****************************************************
*
* Fonctions qui ont au plus une inversion. OK
*
* Les 2 generateurs sont
* (1 2 3 ... n-1 n)    (1 2 3 ... n-2 n-1 n)
* (2 3 4 ... n   1)    (1 2 3 ... n-2 n   -)
*
* L'ordre du monoide est 1 + n/2 * Binomial(2n, n).
*
*****************************************************/

void POPIn(unsigned short n)
{
  short q;
  unsigned long T;
  
  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 2;
  Choix();
  AlloueMemoireGenerateurs();
  
  if (NbEtats > 1)
  {
    for (q = 1; q < NbEtats - 1; q++)
    {
      ((Transitions)Generateurs[0])[q] = q+1;
      ((Transitions)Generateurs[1])[q] = q;      
    }
    ((Transitions)Generateurs[0])[NbEtats - 1] = NbEtats;
    ((Transitions)Generateurs[1])[NbEtats - 1] = NbEtats;      
    ((Transitions)Generateurs[0])[NbEtats] = 1;
    ((Transitions)Generateurs[1])[NbEtats] = 0;
  }
  else if (NbEtats == 1)
  {
    ((Transitions)Generateurs[0])[1] = 1;
    ((Transitions)Generateurs[1])[1] = 0;
  }

  
  T = 2;
  for (q = 2; q <= NbEtats; q++)
  {
    T = 2 * (2 * q - 1) * T;
    T = ceil(T / q);
  }
  TailleMaxi = 1+ (n * T) / 2;
}

/****************************************************
*
* Le groupe cyclique Z/nZ. OK
*
*****************************************************/

void ZnZ(unsigned short n)
{
  unsigned short q;
  
  TypeSemigroupe = ParTransitions;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 1;
  Choix();
  AlloueMemoireGenerateurs();
  
  for (q = 1; q < NbEtats; q++)
    ((Transitions)Generateurs[0])[q] = q+1;
  ((Transitions)Generateurs[0])[NbEtats] = 1;

  TailleMaxi = (numero)n + 2;
}

/******************************************************************************
*
* Le semigroupe RBn engendre par les 4 relations suivantes.
* Ce semigroupe contient tous les elements reguliers de Bn
* Les 4 generateurs sont
* (1 2 3 ... n-1 n)    (1 2 3 ... n-1 n)    (1 2 3 ... n-1   n  )    (1 2 3 ... n-1 n)
* (2 3 4.. . n   1)   (2 1 3 ... n-1 n)    (1 2 3 ... n-1 {n,1})    (1 2 3 ... n-1 -)
*
* L'ordre du monoide est .
*
*******************************************************************************/

void RBn(unsigned short n)
{
  short p, q;
  
  TypeSemigroupe = MatricesBooleennes;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = 4;
  Choix();
  AlloueMemoireGenerateurs();
  
  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
    {
      ((MatriceBooleenne)Generateurs[0])[p][q] = (q == (p+1) % n) ? 1 : 0;
      ((MatriceBooleenne)Generateurs[1])[p][q] = (p == q) ? 1 : 0;
      ((MatriceBooleenne)Generateurs[2])[p][q] = (p == q) ? 1 : 0;
      ((MatriceBooleenne)Generateurs[3])[p][q] = (p == q) ? 1 : 0; 
    }

  ((MatriceBooleenne)Generateurs[1])[0][0] = 0;
  ((MatriceBooleenne)Generateurs[1])[0][1] = 1;
  ((MatriceBooleenne)Generateurs[1])[1][0] = 1;
  ((MatriceBooleenne)Generateurs[1])[1][1] = 0;

  ((MatriceBooleenne)Generateurs[2])[NbEtats-1][0] = 1; 

  ((MatriceBooleenne)Generateurs[3])[NbEtats-1][NbEtats-1] = 0; 
  TailleMaxi = 63904;
}

/****************************************************
*
* Le monoide des matrices booleennes unitriangulaires. OK
*
*****************************************************/

void Un(unsigned short n)
{
  short p, q;
  lettre a;

  TypeSemigroupe = MatricesBooleennes;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = (n * (n-1)) / 2;
  Choix();
  AlloueMemoireGenerateurs();
  
  for (a = 0; a < NbLettres; a++)
    for (p = 0; p < NbEtats; p++)
      for (q = 0; q < NbEtats; q++)
          ((MatriceBooleenne)Generateurs[a])[p][q] = (p != q) ? 0 : 1;
  for (p = 0; p < NbEtats; p++)    
    for (q = p+1; q < NbEtats; q++)
      ((MatriceBooleenne)Generateurs[q + (p * n) - (((p + 1) * (p + 2)) / 2)])[p][q] = 1;
  TailleMaxi = ldexp(1, NbLettres);
}

/****************************************************
*
* Le monoide des matrices booleennes triangulaires. OK
*
*****************************************************/

void Trn(unsigned short n)
{
  short p, q;
  lettre a;

  TypeSemigroupe = MatricesBooleennes;
  TypeCalcul = Monoide;
  NbEtats = n;
  NbLettres = (n * (n+1)) / 2;
  Choix();
  AlloueMemoireGenerateurs();
  
  for (a = 0; a < NbLettres; a++)
    for (p = 0; p < NbEtats; p++)
      for (q = 0; q < NbEtats; q++)
          ((MatriceBooleenne)Generateurs[a])[p][q] = (p != q) ? 0 : 1;
  for (p = 0; p < NbEtats; p++)    
    for (q = p+1; q < NbEtats; q++)
      ((MatriceBooleenne)Generateurs[q + (p * n) - (((p + 1) * (p + 2)) / 2)])[p][q] = 1;
  for (p = 0; p < NbEtats; p++)    
      ((MatriceBooleenne)Generateurs[((n * (n-1)) / 2) + p])[p][p] = 0;
  TailleMaxi = ldexp(1, NbLettres);
}

/****************************************************
*
* Le monoide engendre par les matrices 1 0  et  1 1  
*                                      1 1      0 1
*****************************************************/

void DeuxPetitesMatrices(short s, short p)
{
  TypeSemigroupe = MatricesEntieres;
  TypeCalcul = Monoide;
  Seuil = s;
  Periode = p;
  NbLettres = 2;
  NbEtats = 2;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Matrice)Generateurs[0])[0][0] = 1;
  ((Matrice)Generateurs[0])[0][1] = 0;
  ((Matrice)Generateurs[0])[1][0] = 1;
  ((Matrice)Generateurs[0])[1][1] = 1;
  
  ((Matrice)Generateurs[1])[0][0] = 1;
  ((Matrice)Generateurs[1])[0][1] = 1;
  ((Matrice)Generateurs[1])[1][0] = 0;
  ((Matrice)Generateurs[1])[1][1] = 1;

  TailleMaxi = (s + p) * (s + p) * (s + p);
}

/****************************************************
*
* Un semigroupe de LJ qui n'est pas dans B1. OK
*
*****************************************************/

void ExempleNonKnast(void)
{
  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Semigroupe;
  NbLettres = 4;
  NbEtats = 7;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Transitions)Generateurs[0])[0] = 0;
  ((Transitions)Generateurs[0])[1] = 4;
  ((Transitions)Generateurs[0])[2] = 4;
  ((Transitions)Generateurs[0])[3] = 0;
  ((Transitions)Generateurs[0])[4] = 0;
  ((Transitions)Generateurs[0])[5] = 0;
  ((Transitions)Generateurs[0])[6] = 0;
  ((Transitions)Generateurs[0])[7] = 4;

  ((Transitions)Generateurs[1])[0] = 0;
  ((Transitions)Generateurs[1])[1] = 0;
  ((Transitions)Generateurs[1])[2] = 2;
  ((Transitions)Generateurs[1])[3] = 0;
  ((Transitions)Generateurs[1])[4] = 2;
  ((Transitions)Generateurs[1])[5] = 5;
  ((Transitions)Generateurs[1])[6] = 5;
  ((Transitions)Generateurs[1])[7] = 0;

  ((Transitions)Generateurs[2])[0] = 0;
  ((Transitions)Generateurs[2])[1] = 0;
  ((Transitions)Generateurs[2])[2] = 0;
  ((Transitions)Generateurs[2])[3] = 3;
  ((Transitions)Generateurs[2])[4] = 7;
  ((Transitions)Generateurs[2])[5] = 0;
  ((Transitions)Generateurs[2])[6] = 3;
  ((Transitions)Generateurs[2])[7] = 7;

  ((Transitions)Generateurs[3])[0] = 0;
  ((Transitions)Generateurs[3])[1] = 0;
  ((Transitions)Generateurs[3])[2] = 6;
  ((Transitions)Generateurs[3])[3] = 6;
  ((Transitions)Generateurs[3])[4] = 0;
  ((Transitions)Generateurs[3])[5] = 6;
  ((Transitions)Generateurs[3])[6] = 0;
  ((Transitions)Generateurs[3])[7] = 0;

  TailleMaxi = 31;
/*  AlloueMemoireFinaux(); 
  EtatsFinaux[3] = 1;  */
}

/****************************************************
*
* Un exemple de transitions. OK
*
*****************************************************/

/* void ExempleTransitions(void)
{
  TypeSemigroupe = ParTransitions;
  TypeCalcul = Semigroupe;
  NbLettres = 3;
  NbEtats = 4;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Transitions)Generateurs[0])[1] = 1;
  ((Transitions)Generateurs[0])[2] = 3;
  ((Transitions)Generateurs[0])[3] = 4;
  ((Transitions)Generateurs[0])[4] = 4;
  
  ((Transitions)Generateurs[1])[1] = 2;
  ((Transitions)Generateurs[1])[2] = 4;
  ((Transitions)Generateurs[1])[3] = 3;
  ((Transitions)Generateurs[1])[4] = 4;

  ((Transitions)Generateurs[2])[1] = 4;
  ((Transitions)Generateurs[2])[2] = 1;
  ((Transitions)Generateurs[2])[3] = 2;
  ((Transitions)Generateurs[2])[4] = 4;

  TailleMaxi = 100;
} */

/****************************************************
*
* Un exemple de transitions. OK
*
*****************************************************/

void ExempleTransitions(void)
{
  TypeSemigroupe = ParTransitionsPartielles;
  TypeCalcul = Semigroupe;
  NbLettres = 2;
  NbEtats = 5;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Transitions)Generateurs[0])[1] = 3;
  ((Transitions)Generateurs[0])[2] = 5;
  ((Transitions)Generateurs[0])[3] = 3;
  ((Transitions)Generateurs[0])[4] = 3;
  ((Transitions)Generateurs[0])[5] = 5;
  
  ((Transitions)Generateurs[1])[1] = 0;
  ((Transitions)Generateurs[1])[2] = 2;
  ((Transitions)Generateurs[1])[3] = 4;
  ((Transitions)Generateurs[1])[4] = 2;
  ((Transitions)Generateurs[1])[5] = 2;

  TailleMaxi = 8;
/*  AlloueMemoireFinaux(); 
  EtatsFinaux[5] = 1;  */
} 

/****************************************************
*
* Un exemple de transitions. OK
*
*****************************************************/

/* void ExempleTransitions(void)
{
  TypeSemigroupe = ParTransitions;
  TypeCalcul = Semigroupe;
  NbLettres = 2;
  NbEtats = 12;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Transitions)Generateurs[0])[1] = 2;
  ((Transitions)Generateurs[0])[2] = 3;
  ((Transitions)Generateurs[0])[3] = 2;
  ((Transitions)Generateurs[0])[4] = 5;
  ((Transitions)Generateurs[0])[5] = 6;
  ((Transitions)Generateurs[0])[6] = 5;
  ((Transitions)Generateurs[0])[7] = 8;
  ((Transitions)Generateurs[0])[8] = 9;
  ((Transitions)Generateurs[0])[9] = 8;
  ((Transitions)Generateurs[0])[10] = 11;
  ((Transitions)Generateurs[0])[11] = 12;
  ((Transitions)Generateurs[0])[12] = 11;
  
  ((Transitions)Generateurs[1])[1] = 4;
  ((Transitions)Generateurs[1])[2] = 4;
  ((Transitions)Generateurs[1])[3] = 4;
  ((Transitions)Generateurs[1])[4] = 7;
  ((Transitions)Generateurs[1])[5] = 7;
  ((Transitions)Generateurs[1])[6] = 7;
  ((Transitions)Generateurs[1])[7] = 10;
  ((Transitions)Generateurs[1])[8] = 10;
  ((Transitions)Generateurs[1])[9] = 10;
  ((Transitions)Generateurs[1])[10] = 4;
  ((Transitions)Generateurs[1])[11] = 4;
  ((Transitions)Generateurs[1])[12] = 4;

  TailleMaxi = 12;
} */

/****************************************************
*
* Un exemple de transitions. OK
*
*****************************************************/

/* void ExempleTransitions(void)
{
  TypeSemigroupe = ParTransitions;
  TypeCalcul = Monoide;
  NbLettres = 2;
  NbEtats = 6;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Transitions)Generateurs[0])[1] = 3;
  ((Transitions)Generateurs[0])[2] = 4;
  ((Transitions)Generateurs[0])[3] = 4;
  ((Transitions)Generateurs[0])[4] = 0;
  ((Transitions)Generateurs[0])[5] = 0;
  ((Transitions)Generateurs[0])[6] = 5;
  
  ((Transitions)Generateurs[1])[1] = 0;
  ((Transitions)Generateurs[1])[2] = 6;
  ((Transitions)Generateurs[1])[3] = 1;
  ((Transitions)Generateurs[1])[4] = 2;
  ((Transitions)Generateurs[1])[5] = 6;
  ((Transitions)Generateurs[1])[6] = 0;

  TailleMaxi = 18;
} */

/****************************************************
*
* Un exemple de matrices booleennes. OK
*
*****************************************************/

void ExempleMatricesBooleennes(void)
{
  TypeSemigroupe = MatricesBooleennes;
  TypeCalcul = Monoide;
  NbLettres = 2;
  NbEtats = 3;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((MatriceBooleenne)Generateurs[0])[0][0] = 0;
  ((MatriceBooleenne)Generateurs[0])[0][1] = 1;
  ((MatriceBooleenne)Generateurs[0])[0][2] = 0;
  ((MatriceBooleenne)Generateurs[0])[1][0] = 1;
  ((MatriceBooleenne)Generateurs[0])[1][1] = 1;
  ((MatriceBooleenne)Generateurs[0])[1][2] = 0;
  ((MatriceBooleenne)Generateurs[0])[2][0] = 0;
  ((MatriceBooleenne)Generateurs[0])[2][1] = 1;
  ((MatriceBooleenne)Generateurs[0])[2][2] = 0;
  
  ((MatriceBooleenne)Generateurs[1])[0][0] = 1;
  ((MatriceBooleenne)Generateurs[1])[0][1] = 0;
  ((MatriceBooleenne)Generateurs[1])[0][2] = 0;
  ((MatriceBooleenne)Generateurs[1])[1][0] = 1;
  ((MatriceBooleenne)Generateurs[1])[1][1] = 0;
  ((MatriceBooleenne)Generateurs[1])[1][2] = 1;
  ((MatriceBooleenne)Generateurs[1])[2][0] = 1;
  ((MatriceBooleenne)Generateurs[1])[2][1] = 0;
  ((MatriceBooleenne)Generateurs[1])[2][2] = 0;

  TailleMaxi = 7;
}

/****************************************************
*
* Un exemple de matrices dans Z_{s,p}. OK
*
*****************************************************/

void ExempleMatricesEntieres(void)
{
  TypeSemigroupe = MatricesEntieres;
  TypeCalcul = Monoide;
  Seuil = 1;
  Periode = 2;
  NbLettres = 2;
  NbEtats = 3;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Matrice)Generateurs[0])[0][0] = 0;
  ((Matrice)Generateurs[0])[0][1] = 1;
  ((Matrice)Generateurs[0])[0][2] = 0;
  ((Matrice)Generateurs[0])[1][0] = 1;
  ((Matrice)Generateurs[0])[1][1] = 1;
  ((Matrice)Generateurs[0])[1][2] = 0;
  ((Matrice)Generateurs[0])[2][0] = 0;
  ((Matrice)Generateurs[0])[2][1] = 1;
  ((Matrice)Generateurs[0])[2][2] = 0;
  
  ((Matrice)Generateurs[1])[0][0] = 1;
  ((Matrice)Generateurs[1])[0][1] = 0;
  ((Matrice)Generateurs[1])[0][2] = 0;
  ((Matrice)Generateurs[1])[1][0] = 1;
  ((Matrice)Generateurs[1])[1][1] = 0;
  ((Matrice)Generateurs[1])[1][2] = 1;
  ((Matrice)Generateurs[1])[2][0] = 1;
  ((Matrice)Generateurs[1])[2][1] = 0;
  ((Matrice)Generateurs[1])[2][2] = 0;

  TailleMaxi = 37;
}


/****************************************************
*
* Un exemple de matrices Max-Plus. OK
*
*****************************************************/

void ExempleMatricesMaxPlus(void)
{
  TypeSemigroupe = MatricesMaxPlus;
  TypeCalcul = Semigroupe;
  NbLettres = 2;
  NbEtats = 2;
  Choix();
  AlloueMemoireGenerateurs();

  ((Matrice)Generateurs[0])[0][0] = 0;
  ((Matrice)Generateurs[0])[0][1] = -4;
  ((Matrice)Generateurs[0])[1][0] = -4;
  ((Matrice)Generateurs[0])[1][1] = -1;

  ((Matrice)Generateurs[1])[0][0] = 0;
  ((Matrice)Generateurs[1])[0][1] = -3;
  ((Matrice)Generateurs[1])[1][0] = -3;
  ((Matrice)Generateurs[1])[1][1] = -1;

  TailleMaxi = 27;
}

/****************************************************
*
* Un exemple de matrices Max-Plus projectives. Fourni
* par Jean-Paul Comet. Ne marche pas...
*
*****************************************************/

void ExempleMatMaxPlusProjectives(void)
{
  TypeSemigroupe = MatricesMaxPlusProjectives;
  TypeCalcul = Monoide;
  NbLettres = 3;
  NbEtats = 5;
  Choix();
  AlloueMemoireGenerateurs();

  ((Matrice)Generateurs[0])[0][0] = 0;
  ((Matrice)Generateurs[0])[0][1] = -1;
  ((Matrice)Generateurs[0])[0][2] = -2;
  ((Matrice)Generateurs[0])[0][3] = -3;
  ((Matrice)Generateurs[0])[0][4] = -4;

  ((Matrice)Generateurs[0])[1][0] = LONG_MIN;
  ((Matrice)Generateurs[0])[1][1] = -1;
  ((Matrice)Generateurs[0])[1][2] = 0;
  ((Matrice)Generateurs[0])[1][3] = -1;
  ((Matrice)Generateurs[0])[1][4] = -2;

  ((Matrice)Generateurs[0])[2][0] = LONG_MIN;
  ((Matrice)Generateurs[0])[2][1] = LONG_MIN;
  ((Matrice)Generateurs[0])[2][2] = -1;
  ((Matrice)Generateurs[0])[2][3] = 0;
  ((Matrice)Generateurs[0])[2][4] = -1;

  ((Matrice)Generateurs[0])[3][0] = LONG_MIN;
  ((Matrice)Generateurs[0])[3][1] = LONG_MIN;
  ((Matrice)Generateurs[0])[3][2] = LONG_MIN;
  ((Matrice)Generateurs[0])[3][3] = -1;
  ((Matrice)Generateurs[0])[3][4] = -1;
  
  ((Matrice)Generateurs[0])[4][0] = LONG_MIN;
  ((Matrice)Generateurs[0])[4][1] = LONG_MIN;
  ((Matrice)Generateurs[0])[4][2] = LONG_MIN;
  ((Matrice)Generateurs[0])[4][3] = LONG_MIN;
  ((Matrice)Generateurs[0])[4][4] = -1; 

  ((Matrice)Generateurs[1])[0][0] = 0;
  ((Matrice)Generateurs[1])[0][1] = 0;
  ((Matrice)Generateurs[1])[0][2] = -1;
  ((Matrice)Generateurs[1])[0][3] = -2;
  ((Matrice)Generateurs[1])[0][4] = -3;

  ((Matrice)Generateurs[1])[1][0] = LONG_MIN;
  ((Matrice)Generateurs[1])[1][1] = -1;
  ((Matrice)Generateurs[1])[1][2] = -1;
  ((Matrice)Generateurs[1])[1][3] = -2;
  ((Matrice)Generateurs[1])[1][4] = -3;

  ((Matrice)Generateurs[1])[2][0] = LONG_MIN;
  ((Matrice)Generateurs[1])[2][1] = LONG_MIN;
  ((Matrice)Generateurs[1])[2][2] = -1;
  ((Matrice)Generateurs[1])[2][3] = -1;
  ((Matrice)Generateurs[1])[2][4] = -2;

  ((Matrice)Generateurs[1])[3][0] = LONG_MIN;
  ((Matrice)Generateurs[1])[3][1] = LONG_MIN;
  ((Matrice)Generateurs[1])[3][2] = LONG_MIN;
  ((Matrice)Generateurs[1])[3][3] = -1;
  ((Matrice)Generateurs[1])[3][4] = 0;
  
  ((Matrice)Generateurs[1])[4][0] = LONG_MIN;
  ((Matrice)Generateurs[1])[4][1] = LONG_MIN;
  ((Matrice)Generateurs[1])[4][2] = LONG_MIN;
  ((Matrice)Generateurs[1])[4][3] = LONG_MIN;
  ((Matrice)Generateurs[1])[4][4] = -1; 

  ((Matrice)Generateurs[2])[0][0] = 0;
  ((Matrice)Generateurs[2])[0][1] = -1;
  ((Matrice)Generateurs[2])[0][2] = -2;
  ((Matrice)Generateurs[2])[0][3] = -3;
  ((Matrice)Generateurs[2])[0][4] = -4;

  ((Matrice)Generateurs[2])[1][0] = LONG_MIN;
  ((Matrice)Generateurs[2])[1][1] = -1;
  ((Matrice)Generateurs[2])[1][2] = -1;
  ((Matrice)Generateurs[2])[1][3] = -2;
  ((Matrice)Generateurs[2])[1][4] = -3;

  ((Matrice)Generateurs[2])[2][0] = LONG_MIN;
  ((Matrice)Generateurs[2])[2][1] = LONG_MIN;
  ((Matrice)Generateurs[2])[2][2] = -1;
  ((Matrice)Generateurs[2])[2][3] = -1;
  ((Matrice)Generateurs[2])[2][4] = -2;

  ((Matrice)Generateurs[2])[3][0] = LONG_MIN;
  ((Matrice)Generateurs[2])[3][1] = LONG_MIN;
  ((Matrice)Generateurs[2])[3][2] = LONG_MIN;
  ((Matrice)Generateurs[2])[3][3] = -1;
  ((Matrice)Generateurs[2])[3][4] = -1;
  
  ((Matrice)Generateurs[2])[4][0] = LONG_MIN;
  ((Matrice)Generateurs[2])[4][1] = LONG_MIN;
  ((Matrice)Generateurs[2])[4][2] = LONG_MIN;
  ((Matrice)Generateurs[2])[4][3] = LONG_MIN;
  ((Matrice)Generateurs[2])[4][4] = -1; 

  TailleMaxi = 30000;
}

/****************************************************
*
* Un autre exemple de matrices dans Z_{s,p}. OK
*
*****************************************************/

/*
void ExempleMatricesEntieres(void)
{
  TypeSemigroupe = MatricesEntieres;
  TypeCalcul = Monoide;
  Seuil = 3;
  Periode = 1;
  NbLettres = 2;
  NbEtats = 2;
  Choix();
  AlloueMemoireGenerateurs();
  
  ((Matrice)Generateurs[0])[0][0] = 1;
  ((Matrice)Generateurs[0])[0][1] = 0;
  ((Matrice)Generateurs[0])[1][0] = 2;
  ((Matrice)Generateurs[0])[1][1] = 1;
  
  ((Matrice)Generateurs[1])[0][0] = 1;
  ((Matrice)Generateurs[1])[0][1] = 1;
  ((Matrice)Generateurs[1])[1][0] = 0;
  ((Matrice)Generateurs[1])[1][1] = 2;

  TailleMaxi = 12;
}
*/