Inv. 02031

RIA
laboria

laboratoire de recherche
en informatique
et automatique

Minimisation
des machines séquentielles
incomplètement spécifiées

G.Michel

51p

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 70

mai 1974
MINIMISATION DES MACHINES
SÉQUENTIELLES INCOMPLETEMENT
SPÉCIFIÉES

G. Michel

(présenté par M. Depeyrot)

Le schéma de contrôle d'un algorithme se distingue d'un automate pour deux raisons, l'une fondamentale et peu conséquente, l'autre non systématique mais très conséquente.

La première est qu'un algorithme dispose d'un état initial et d'un état final (de repos). La seconde est que la plupart des algorithmes sont des machines séquentielles "incomplètement spécifiées", c'est-à-dire que certaines paires (Etat, Entrée) ne sont pas définies. En conséquence, les études théoriques des automates ne sont pas directement applicables au contrôle des algorithmes, ce qui en limite l'intérêt alors même que le développement de la microprogrammation, par exemple, accroît l'importance d'éventuels résultats [11].

Dans le cas de la minimisation qui nous concerne ici, différentes méthodes, destinées à appliquer aux algorithmes les techniques des automates ont été publiées sous la forme de contributions limitées à diverses procédures partielles ou complètes ([1] à [4], [7], [8]).

Le but de cet article est de rassembler les nombreuses idées connues sous forme d'une procédure unique qui ajoute l'avantage de ne jamais nécessiter de retour en arrière dans l'élaboration de la solution. En outre la procédure synthétique présentée ici est une solution complète du problème de la minimisation des machines séquentielles incomplètement spécifiées.
Summary

The control scheme of an algorithm is distinguished
from an automaton for two reasons, one being fundamental although of
little consequence, the other being not systematic but very consequent.
The former is that an algorithm is given an initial state and a final
 rest) state. The latter is that most algorithms are "incompletely
specified" sequential machines, i.e. that some (State, Input) pairs
are undefined. Consequently, theoretical studies of automata are not
directly applicable to algorithm control, which limits their interest
even though the development of microprogramming, for instance, increa-
ses the importance of eventual results [11].

In the case of minimization which is our concern here,
different methods, for applying to algorithms automaton techniques,
have been published as limited contributions to various procedures
partial or incomplete ([1] to [4], [7], [8]).

The aim of this article is to gather numerous known
ideas under a single procedure that adds the advantage of never re-
quiring back-up. Moreover this synthetic procedure is a complete
solution of the minimization problem of incompletely specified se-
quential machines.
TABLE DES MATIERES

<table><thead><tr><th>paragraphe</th><th>Titre</th><th>page</th></tr></thead><tbody><tr><td>I.</td><td>Introduction aux machines "Transition-sortie"</td><td>1</td></tr><tr><td></td><td>I. 1 Machine de Mealy</td><td>1</td></tr><tr><td></td><td>I. 2 Notion de machine incomplètement spécifiée</td><td>1</td></tr><tr><td>II.</td><td>Minimisation ; Notion de Compatible</td><td>2</td></tr><tr><td>III.</td><td>Algorithme de Recherche des Compatibles</td><td>6</td></tr><tr><td>IV.</td><td>Compatibles Maximaux (C. M.)</td><td>8</td></tr><tr><td></td><td>IV. 1 Algorithme de recherche des C. M.</td><td>8</td></tr><tr><td></td><td>IV. 2 Second Algorithme de génération des C. M.</td><td>9</td></tr><tr><td>V.</td><td>Les classes de Compatibilite premières (Q-CCP)</td><td>11</td></tr><tr><td></td><td>V. 1 Algorithme de Recherche des Q-CCP</td><td>12</td></tr><tr><td></td><td>V. 2 Exemple 6</td><td>12</td></tr><tr><td>VI.</td><td>Algorithme de Meisel</td><td>14</td></tr><tr><td></td><td>VI. 1 Définitions préliminaires</td><td>14</td></tr><tr><td></td><td>VI. 2 Présentation de l'algorithme</td><td>14</td></tr><tr><td>VII.</td><td>Procédure de réduction lignes-colonnes</td><td>19</td></tr><tr><td>VIII.</td><td>Conclusion</td><td>26</td></tr><tr><td></td><td>ANNEXES</td><td>27</td></tr><tr><td></td><td>Bibliographie</td><td>30</td></tr><tr><td></td><td>Appendice. Programme PAU</td><td>31</td></tr></tbody></table>
LISTE DES EXEMPLES

<table><thead><tr><td>Exemple n°</td><td>Titre</td><td>page</td></tr></thead><tbody><tr><td>1</td><td>Table d'une machine incomplètement spécifiée...</td><td>2</td></tr><tr><td>2</td><td>Ensemble d'états implique....................</td><td>4</td></tr><tr><td>3</td><td>Algorithme de recherche des compatibles.........</td><td>7</td></tr><tr><td>4</td><td>Recherche des compatibles maximaux (C. M.).....</td><td>8</td></tr><tr><td>5</td><td>Matrice des Compatibles.......................</td><td>9</td></tr><tr><td>6</td><td>Formation de la table des Implicants premiers (C-CCP).................................</td><td>12</td></tr><tr><td>7</td><td>Second algorithme des C-CCP....................</td><td>15</td></tr><tr><td>8</td><td>Algorithme de Meisel.........................</td><td>16</td></tr><tr><td>9</td><td>Exemple d'application complet..................</td><td>17</td></tr></tbody></table>
# I. INTRODUCTION AUX MACHINES "TRANSITION-SORTIE".

## I. 1. MACHINE DE MEALY

Une machine de Mealy est un quintuple $M = (U, Q, Y, \tau, \lambda)$
avec $U$: Alphabet d'entrée
$Q$: Espace d'états
$Y$: Espace de sortie.
$\tau$: $Q \times U \to Q$ fonction de transition.
$\lambda$: $Q \times U \to Y$ fonction de sortie.

La machine $M$ dans l'état $q_i$, sous l'action de $u_j$ va
dans l'état $\tau$ ($q_i, u_j$) = $q_{ij}$ en fournissant la sortie $\lambda$ ($q_i, u_j$)=$y_{ij}$
Elle est donc en forme Transition/Sortie.

Le quintuple $M = (U, Q, Y, \tau, \lambda)$ est entièrement défini
par la table de fluence de la machine.

A l'ensemble $Q$ des états de la machine correspondent les
lignes (i) de la table. Aux entrées (ou "actions") les colonnes (j).
Les états $\{q_i\}$ sont repérés par l'indice de ligne de la table de flu-
ence, les entrées $\{u_j\}$ par l'indice de colonne.

### Notation

$U^*$ représente l'ensemble des séquences d'entrée de longueur
quelconque.

Les éléments de la table sont de la forme :

état suivant, sortie.

## I. 2. NOTION DE MACHINE INCOMPIETEMENT SPECIFIÉE.

**Définition** Une machine $M$ incomplètement spécifiée est
une machine dans laquelle au moins un état suivant $q_{ij} = \tau(q_i, u_j)$
ou une sortie $y_{ij} = \lambda(q_i, u_j)$ n'est pas précisée. Sa "valeur" est
alors représentée par le symbole : -
**Exemple 1.** Table d'une machine incomplètement spécifiée.

(l'état $q_i$ est noté "i")

entrée

<table><thead><tr><th></th><th>$u_1$</th><th>$u_2$</th></tr></thead><tbody><tr><th>1</th><td>2, -</td><td>2,0</td></tr><tr><th>2</th><td>-, 1</td><td>3,1</td></tr><tr><th>3</th><td>-, -</td><td>1, -</td></tr></tbody></table>

**Représentation matricielle** : Les définitions posées en [6] nous permettent d'introduire une représentation équivalente à la table de fluence :

$$ \mathcal{M}[u_1] = \begin{bmatrix} 0 & 1 & 0 \\ - & - & - \\ - & - & - \end{bmatrix} \quad ; \quad \mathcal{M}[u_2] = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \quad \text{pour l'opérande} $$

et une matrice d'agrégation par entrée :

$$ A(u_1) = \begin{bmatrix} - & - \\ 0 & 1 \\ - & - \end{bmatrix} \quad ; \quad A(u_2) = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ - & - \end{bmatrix} $$

## II. MINIMISATION ; NOTION DE "COMPATIBLE". [1].

Q- Réduire une machine M c'est trouver une machine M'
telle que $|C'| < |C|$

($|Q|$ représente le cardinal de $C$), de même alphabet d'entrée que M et fournissant même séquence de sortie que M pour toute séquence d'entrée.
**Définition** Une machine $M_m$. C- minimale est une machine d'espace d'état $Q_m$ tel que $|C_m| = \text{Inf} (\{|Q'_i|\}) \{Q'_1\}$ étant l'ensemble des espaces d'état des machines Q- Réduites $M'$.

Au sens de [5] les machines $M$ et $M'$ sont équivalentes.

Introduisons la notion de transition pour une séquence d'entrée :
sous l'action de $u_{i_1}$, l'état $q$ de $M$ va en $q_{i_1}$ :

$$ \tau : q \longrightarrow q_{i_1} = \tau (q, u_{i_1}) $$

$$ \text{puis} \qquad q_{i_1} \longrightarrow q_{i_2} = \tau (q_{i_1}, u_{i_2}) = \tau [\tau(q, u_{i_1}), u_{i_2}] \stackrel{\Delta}{=} \tau (q, u_{i_1}, u_{i_2}) $$

en généralisant :

$$ u^* = u_{i_1} u_{i_2} \dots u_{i_{p-1}} $$

$$ \tau [ \tau(q, u^*), u_{i_p} ] \stackrel{\Delta}{=} \tau (q, u^* u_{i_p}) $$

Ce qui nous permet de poser :

**Définition** Une table de fluence **M** recouvre une table de fluence **M'** (machines ayant même alphabets d'entrée) si pour tout état $q'$ de **M** il existe un état $q$ de **M** tel que, pour toute séquence d'entrée $u^* \in U^*$, la sortie résultante de **M** est identique à celle de **M**'.

$$ Vq' \in Q', \quad Eq \in Q \text{ tel que } Vu^* \in U^* \Rightarrow \lambda' (q', u^*) = \lambda (q, u^*) $$

Les états $q$ et $q'$ précédents sont dits équivalents.

Il est équivalent de dire : La table de M recouvre celle de $M'$ et $M'$ est une machine Q-Réduite de M.

**Définition** On appelle recouvrement d'un ensemble $C$, tout ensemble de n sous-ensembles $C_i$ ($i = 1, ..., n$) de $C$ tel que : $U = \bigcup_{i=1,...,p} C_i = Q$

**Remarque** : Une partition est un recouvrement tel que

$$ C_i \cap C_j = \emptyset $$

$$ V_i = 1, ..., n $$

$$ i \neq j $$

$$ V_j = 1, ..., n $$
Recouvrement et partition sont représentables par des matrices d'agré-
gation. Considérons l'ensemble d'états 1, 2, 3, 4, 5 et un recouvrement
123, 345, alors :

$$
A_R = \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 0 & 1 \end{bmatrix} \quad \text{tandis que la partition 12, 345 conduit à :}
$$

$$
A_P = \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{bmatrix} \quad \text{qui est une matrice monomiale en ligne.}
$$

**Définition.** Un ensemble d'états P ⊆ Q est impliqué pour u_k par un ensemble d'états R ⊆ Q si il existe une entrée u_k telle que :

$$
\forall p \in P, \quad \exists r \in R \text{ tel que } p = \tau_{\_}(r, u_k)
$$

Nous noterons cette implication : $P = \mathcal{J}_{u_k}(R) = \mathcal{J}_k(R)$

**Exemple 2.** Ensemble d'états impliqués.

Reprenons la table de fluence de l'exemple précédent. L'ensemble

$$
P = \{3, 1\} \text{ est impliqué par } R = \{2, 3\} \text{ puisque :}
$$

$$
P = \{\tau (2, u_2), \tau (3, u_2)\} = \mathcal{J}_{u_2} (R)
$$

Dans le cas où $\mathcal{J}_{u_k}(R)$ est complètement inspécifié nous écrirons :

$$
\mathcal{J}_{u_k}(R) = \emptyset
$$

Matriciellement, l'ensemble des états impliqués pour $u_k$, par l'ensemble
R écrit sous forme de vecteurs ligne est obtenu par multiplication à
gauche de $\mathcal{M}(u_k)$

$$
\text{pour } R = \{2, 3\} \Rightarrow R = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}
$$

$$
\text{et } u_2 \qquad \mathcal{M}(u_2) = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}
$$
$$ \text{alors } P = R. \quad \mathcal{M}(u_2) = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} $$

Soit $P = \{3, 1\}$

**Définition.** Un recouvrement $\{C_i\}$ est dit **fermé** si
1) $\forall i, k$ ; $\exists j$ tel que $J_k(C_i) \subseteq C_j$

2) $\forall p \text{ et } t \in C_i, \exists i, \forall k : \lambda(p, u_k) = \lambda(t, u_k)$
si les deux sont définis.

En d'autres termes $C_i \mathcal{M}(u_k)$ est une sous-matrice d'un certain $C_j$ et les éléments de $C_i$ appartiennent au même élément de la partition de l'espace image par $u_k$ du recouvrement, induite par $A(u_k)$.

**Théorème 1.** Toute forme réduite d'une table de fluence est obtenue par substitution à l'ensemble de ses états d'un recouvrement fermé.

Démonstration en Annexe.

Nous nous attachons maintenant à la recherche des recouvrements fermés d'un ensemble d'états Q d'une machine M.

**Définition.** Un compatible est un couple d'états d'une table de fluence, élément d'un recouvrement fermé.
Un couple est incompatible s'il n'est pas compatible.

**Définition.** Une classe de compatibilité est un ensemble d'états d'une table de fluence, élément d'un recouvrement fermé.
Ainsi un compatible est une classe de compatibilité à deux états.

**Théorème 2.** Un ensemble d'états est une classe de compatibilité si et seulement si il est formé de compatibles.

Démonstration en Annexe.

**Définition.** Une **chaîne** générée par un ensemble d'états $B \subset Q$ est la collection de tous les ensembles produits par le processus récursif suivant :
1) B appartient à la chaîne.

2) si R appartient à la chaîne, $J_k(R)$, $v_k$ est ajouté à la chaîne.

Les théorèmes et définitions précédents conduisent au théorème ci-dessous, qui donne un moyen pratique de construire les classes de compatibilité cherchées.

**Théorème 3.** Un ensemble d'états B est une classe de compatibilité si il n'existe pas de sous-ensemble S appartenant à la chaîne générée par B et tel que :

$\exists s_1 \in S, \exists k \text{ tel que } \lambda(s_1, u_k) \text{ et } \lambda(s_2, u_k)$

sont définis et différents.

Démonstration en Annexe.

### III. ALGORITHME DE RECHERCHE DES COMPATIBLES.

La méthode développée en [1] est tabulaire. Pour n états la table d'implication a la forme suivante :

<figure><img src="image_1.png" /></figure>

A chaque couple $(x, y)$ d'états correspond bijectivement une case.

**Algorithme.**

1. Si les sorties sont contradictoires, le couple est incompatible. Mettre X dans la case et passer au suivant.

2. Si les sorties de $(x, y)$ sont égales ou non spécifiées écrire dans la case correspondante les paires impliquées $J_k(x, y)$ pour toutes les entrées $u_k$.
Si $J_0(x,y) = \emptyset$, le symbole V marquera que le couple est in- conditionnellement compatible.

3- Lorsque toutes les cases ont été considérées, faire un second passage en interdisant les couples implicant des incompatibles.

4- Un 2ème passage permet d'interdire (X) les combinaisons implicant des incompatibles.

Les paires restantes sont des compatibles.

**Exemple 3.** Algorithme de recherche des compatibles.

Les états "q<sub>i</sub>" sont notés "i".

<table><thead><tr><th></th><th>u<sub>1</sub></th><th>u<sub>2</sub></th><th>u<sub>3</sub></th><th>u<sub>4</sub></th></tr></thead><tbody><tr><td>1</td><td>2,-</td><td>3,0</td><td>-</td><td>4,-</td></tr><tr><td>2</td><td>3,0</td><td>5,0</td><td>-</td><td>-</td></tr><tr><td>3</td><td>4,-</td><td>6,-</td><td>3,-</td><td>-</td></tr><tr><td>4</td><td>5,1</td><td>3,0</td><td>-</td><td>1,-</td></tr><tr><td>5</td><td>-</td><td>6,0</td><td>-</td><td>-</td></tr><tr><td>6</td><td>-</td><td>-,1</td><td>4,-</td><td>2,-</td></tr></tbody></table>

- les "-" indiquent la non spécification

- les couples sont de la forme : (état, sortie).

**table d'implication** : notation ij...k $\Delta$ Ens $\{q_i, q_j, \dots ; q_k\}$

**Commentaire** : Etude du couple (1, 2). La table de fluence ne montre pas d'impossibilité : toutes les sorties sont concordantes (on ne trouve pas dans une même colonne un couple 0 - 1 ou 1 - 0).

Cependant 1 - 2 implique 2 - 3 en $u_1$ et 3 - 5 en $u_2$.
rien en $u_3$ et $u_4$. 23 et 35 sont reportés dans la case 12.

<table><tbody><tr><td rowspan="2">2</td><td>23</td></tr><tr><td>35</td></tr><tr><td rowspan="2">3</td><td>24</td><td>34</td></tr><tr><td>36</td><td>56</td></tr><tr><td rowspan="2">4</td><td>25</td><td>X</td><td>45</td></tr><tr><td></td><td></td><td>36</td></tr><tr><td rowspan="2">5</td><td>36</td><td>56</td><td>V</td><td>36</td></tr><tr><td></td><td></td><td></td><td></td></tr><tr><td rowspan="2">6</td><td>X</td><td>X</td><td>34</td><td>X</td><td>X</td></tr><tr><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

1 2 3 4 5
Le deuxième passage (étape 3.) conduit à la table suivante,
qu'il est inutile de retracer en pratique :

<figure><img src="image_2.png" /></figure>

Commentaire.

Pour que 12 soit compatible, il faut que 23 et 35 le soient.

Pour que 23 le soit, il faut que
34 et 56 le soient. Or 56 ne l'est
pas (X).

On met un X dans 23 et dans 12.

Et ainsi de suite.

Remarquer que le contenu des cases fournit automatiquement
Pᵢ = {Cᵢⱼ = πⱼ(Cᵢ)}.

#### IV. COMPATIBLES MAXIMAUX [1].

Disposant des compatibles, nous recherchons maintenant des compatibles maximaux. Tout ceci dans le but d'introduire (au § 5) des "classes de compatibilité premières" dont le théorème 4 (cf § 5) nous dit qu'un recouvrement minimal au moins en est formé.

Définition :

Une classe de compatibilité maximum (ou compatible maximum : C. M.) est une classe de compatibilité contenue dans aucune autre.

#### IV. 1 ALGORITHM DE RECHERCHE DES C. M.

Le point de départ est la colonne de droite de la table d'implication (cf § 3).

1. Ecrire la première paire de compatibles.

2. Examiner la colonne suivante (à gauche et portant le numéro k).

Si k est compatible avec chacun des éléments d'une paire précédente, rajouter k à celle-ci. Ajouter à la liste les autres compatibles.

3. Soit f le numéro de la colonne immédiatement à gauche. On applique le 2- ; mais de plus si f est compatible avec un sous-ensemble d'un compatible, ajouter à la liste la réunion de f et du sous-ensemble.

Le processus prend fin après examen de la colonne 1.

Exemple 4 : Recherche des Compatibles Maximaux.

Reprenons la table d'implication de l'exemple 2.
<figure><img src="image_3.png" /></figure>

auxquels il convient de rajouter les 1 isolés.

**Exemple 5 (suite).**

$$ M = \begin{bmatrix} 0 & & & \\ 0 & 0 & & \\ 0 & 0 & 0 & \\ 0 & 0 & 1 & 0 \\ \boxed{1} & 0 & 1 & 1 & 0 \\ 0 & 0 & \boxed{1} & 0 & 0 & 0 \end{bmatrix} \qquad \text{CM} = 3,4,5 \ ; \ 36 \ ; \ 15 $$

Remarquons qu'il est possible de définir une **matrice d'agrégation des compatibles**, $A_c$, où chaque colonne est un compatible formé des états repérés par les lignes à 1.

Pour l'exemple considéré :

$$ A_c = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} $$

ce qui permet d'obtenir les CM. En effet, considérons les colonnes 2,3 et 5 de $A_c$ :

$$ \begin{bmatrix} 2 \\ \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} , & 3 \\ \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} , & 5 \\ \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix} \end{bmatrix} $$

nous voyons que ces compatibles donnent naissance au CM :

$$ a_{cm} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix} $$

Un moyen simple de reconnaître les compatibles agrégables étant de faire la somme des vecteurs colonnes :
$$ \text{ainsi } [2] + [3] + [5] = \begin{bmatrix} 0 \\ 0 \\ 2 \\ 2 \\ 2 \\ 0 \end{bmatrix} = 2 \quad \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix} = 2 a_{cm}. $$

Les autres sommes ne permettent pas de trouver un vecteur de la forme

$$ K \begin{bmatrix} i_1 \\ \vdots \\ i_n \end{bmatrix} \quad \text{où} \quad i_j = 0 \text{ ou } 1 \quad (j = 1, \dots, n) \text{ et } K \in \mathbb{N} $$

## V. LES CLASSES DE COMPATIBILITE PREMIERES [2], [4].

**Définition** : L'ensemble $P_i$ des classes impliquées par $C_i$, classe de compatibilité des états, est l'ensemble $C_{ij}$ (j indice de $u_j$) tels que :

1) $C_{ij}$ a plus d'un élément

2) $C_{ij} \not\le C_{ij'}$ si $C_{ij'} \in P_i$

3) $C_{ij} \not\le C_i$

ce qui s'écrit formellement : $P_i = \{ \overline{\cup_j}(C_i) \}$

$$ P_i \triangleq \{C_{ij} \mid C_{ij} = \overline{\cup_j}(C_i) \setminus C_i, C_{ij} \not\le C_{ij'} \text{ si } C_{ij'} \in P_i\} $$

(avec "\" = "moins").

On notera que $P_i$ exprime la *condition de fermeture*, par rapport aux états de $C_i$.

**Définition** : Une classe de compatibilité $C_i$ est *exclue* par $C_{i2}$ si

1) $C_i \subseteq C_{i2}$

2) $P_i \subseteq P_{i1}$

**Définition** : Une *classe de compatibilité première* est une classe non exclue par toute autre classe de compatibilité.
**Théorème 4.** Un recouvrement minimal (des états) au moins est formé de classes de compatibilité première.

Preuve en Annexe.

C'est là que se trouve donc tout l'intérêt des notions introduites. Il nous reste à trouver les classes de compatibilité première, c'est le but de l'algorithme présenté ci-dessous, et à partir de là de former un recouvrement minimal, c'est ce que fournit l'algorithme de Meisel.

## V. 1. ALGORITHM DE RECHERCHE DES QCCP - Table des implicants premiers.
(Q - Classes de Compatibilité Première)

1. Former le tableau faisant correspondre aux C.M. leurs $P_i$

2. Développer les C.M. en sous-ensembles non exclus et associer les $P_i$

Le tableau obtenu donne les QCCP.

## V. 2. Exemple 6.

Le tableau traité ci-dessous conduit aux C.M. indiquées. Nous laissons au lecteur, à titre d'exercice, le soin de vérifier ces CM en appliquant les méthodes décrites aux § 2, 3, 4.

**remarque** : nous notons $\overline{J}(.)$, l'implication $\overline{J_k}(.)$ pour toutes les entrées k.

**Exemple 6** classes de compatibilité premières, ensemble des classes

$u_1$

$\tilde{u}_2$

$u_3$

$u_4$

$u_5$

$u_6$

$\tilde{u}_7$

<table><tr><td>A</td><td>A,0</td><td>-, -</td><td>D,0</td><td>E,1</td><td>B,0</td><td>A,-</td><td>-, -</td></tr><tr><td>B</td><td>B,0</td><td>D,1</td><td>A,-</td><td>-, -</td><td>A,-</td><td>A,1</td><td>-, -</td></tr><tr><td>C</td><td>B,0</td><td>D,1</td><td>A,1</td><td>-, -</td><td>-, -</td><td>-, -</td><td>G,0</td></tr><tr><td>D</td><td>-, -</td><td>E,-</td><td>-, -</td><td>B,-</td><td>B,0</td><td>-, -</td><td>A,-</td></tr><tr><td>E</td><td>B,-</td><td>E,-</td><td>A,-</td><td>-, -</td><td>B,-</td><td>E,-</td><td>A,1</td></tr><tr><td>F</td><td>B,0</td><td>C,-</td><td>-, 1</td><td>H,1</td><td>F,1</td><td>G,0</td><td>-, -</td></tr><tr><td>G</td><td>-, -</td><td>C,1</td><td>-, -</td><td>E,1</td><td>-, -</td><td>G,0</td><td>F,0</td></tr><tr><td>H</td><td>A,1</td><td>E,0</td><td>D,1</td><td>B,0</td><td>B,-</td><td>E,-</td><td>A,1</td></tr></table>

les CM sont : C,F,G ; D,E,M ; A,B,D,E ; B,C,D ; A,G
1 - Construisons les ensembles de classe associée

<table><thead><tr><th>Classe Max</th><th>Ens classe P<sub>i</sub></th></tr></thead><tbody><tr><td>{ABDE}</td><td>Ø</td></tr><tr><td>{BCD}</td><td>{AB} {AG} {DE}</td></tr><tr><td>{CFG}</td><td>{CD} {EH}</td></tr><tr><td>{DEH}</td><td>{AB} {AD}</td></tr><tr><td>{AG}</td><td>Ø</td></tr></tbody></table>

plus d'un élément

2 - Développons ce tableau.

Nous procédons ici à ce développement en deux étapes pour **souligner** la procédure.

<table><caption>TABLE DES IMPLICANTS PREMIERS</caption><thead><tr><th>QCCP →</th><th>C<sub>i</sub></th><th>P<sub>i</sub> = J(C<sub>i</sub>)</th><th></th></tr></thead><tbody><tr><td></td><td>{A,B,D,E}</td><td>Ø</td><td></td></tr><tr><td></td><td>{B,C,D}</td><td>{A,B} {A,G} {D,E}</td><td rowspan="4">développement des termes {B,C,D}</td></tr><tr><td></td><td>{C,F,G}</td><td>{C,D} {E,H}</td></tr><tr><td></td><td>{D,E,H}</td><td>{A,B} {A,D}</td></tr><tr><td></td><td>{B,C}</td><td>Ø</td></tr><tr><td></td><td>{C,D}</td><td>{A,G} {D,E}</td><td></td></tr><tr><td></td><td>{C,F}</td><td>{C,D}</td><td rowspan="6">développement des autres</td></tr><tr><td></td><td>{C,G}</td><td>{C,D} {F,G}</td></tr><tr><td></td><td>{F,G}</td><td>{E,H}</td></tr><tr><td></td><td>{D,H}</td><td>Ø</td></tr><tr><td></td><td>{A,G}</td><td>Ø</td></tr><tr><td></td><td>{F}</td><td>Ø</td></tr></tbody></table>
Commentaire : 1) {B,D} $\rightarrow$ {A,B} , {D,E}

mais {B,D} $\subset$ {A,B,D,E}

$\emptyset$ $\subset$ {A,B} {D,E}

donc {B,D} est exclu.

2) {F} ajouté car aucune classe avec $P_i$ = $\emptyset$ ne le contient.

VI. ALGORITHM DE MEISEL [3].

Il reste maintenant à trouver un recouvrement minimal.

VI. 1. Définitions préliminaires.

- Un **graphe** est formé de **noeuds** et **d'arêtes**. Les noeuds étant représentés par des points et les arêtes par des segments de droite.

- Une **arête orientée** part d'un **noeud-source** et aboutit à un **noeud-cible**.

- Un chemin est une séquence d'arêtes orientées.

- Une boucle est un chemin fermé.

- Un **branchement** est un ensemble d'arêtes orientées admettant le même noeud-source et aboutissant à des noeuds-cibles différents.

- Une **fusion** est un ensemble d'arêtes orientées partant de noeuds-source distincts pour aboutir au même noeud-cible.

- Un **arbre** est un graphe orienté sans boucle ni fusion.

(graphe orienté = graphe avec arêtes orientées).

- Le **noeud initial** d'un arbre est le noeud-source de la 1ère arête orientée de l'arbre, la numérotation croissant dans le sens de l'orientation.

- Une **chaîne** est un chemin qui part d'un générateur pour aboutir à la fin de l'arbre.

- Une **sous-chaîne** est une partie d'une chaîne.

VI. 2 Présentation de l'Algorithm.

On suppose formée la table des implicants premiers et des $P_i$ correspondants. (Dans l'exemple traité après l'exposé général, nous nous servirons de la table établie au § 5).

1 - Former the table des occurences.

<table><tr><td>Q</td><td>O(Q)</td></tr><tr><td></td><td></td></tr></table>
2 - Prendre l'un des états à occurence minimale dans la table des Q-Classes de compatibilité première (QCCP). Soit $q_0$.

3 - Les générateurs sont les classes $C_i$ contenant l'état $q_0$ :

→ Si le $P_i$ correspondant est vide ou satisfait par les précédents, choisir parmi les états restants celui qui apparaît au minimum (cf 1) et recommencer. Si ils y sont tous : fin de l'algorithme.

→ Si non placer dans des sous-chaînes différentes les combinaisons de QCCP qui satisfont les conditions $P_i$.

**Exemple 7** - (suite de l'exemple 6 p. 12). Les éléments qui apparaissent le moins sont A, E et H. Choisissons A d'où A B D E et A G comme éléments générateurs. (voir graphe p.16)

Etudions l'arbre généré par $A G = C_i(A)$

$P_{AG} = \emptyset$. Choisissons un élément (différent de A) apparaissant au minimum. Soit H qui apparaît dans DEH et DH.

$P_{DEH} = (AB),(AD)$. Une classe de compatibilité première satisfait ces deux conditions : ABDE que nous introduisons dans la chaîne.

**Parallèlement** (important car dès qu'une chaîne satisfait la fermeture, il est inutile de poursuivre) :

$P_{DH} = \emptyset$. Choisissons (comme A et H précédemment) l'état B qui n'apparaît que 3 fois (E a déjà été pris en compte)
il vient $B : A B D E$
$B C D$
$B C$
etc...

A la quatrième étape, la chaîne ABDE, DEH, FG, BC satisfait aux conditions de fermeture $P_{DC}^B = \emptyset$ et tous les éléments ABCDEFGH figurent dans la chaîne recouvrement.

L'algorithme est fini. Il nous reste à réeccrire la table de la machine (cf § 5) en assignant les nouveaux états.

$a = \{ABDE\}$

$b = \{DEH\}$

$d = \{FG\}$

$c = \{BC\}$

<table><thead><tr><th></th><th>u<sub>1</sub></th><th>u<sub>2</sub></th><th>u<sub>3</sub></th><th>u<sub>4</sub></th><th>u<sub>5</sub></th><th>u<sub>6</sub></th><th>u<sub>7</sub></th></tr></thead><tbody><tr><th>a</th><td>a,0</td><td>a,1</td><td>a,0</td><td>a,1</td><td>a,0</td><td>a,-</td><td>a,0</td></tr><tr><th>b</th><td>a,1</td><td>a,0</td><td>a,1</td><td>c,0</td><td>c,0</td><td>b,-</td><td>a,1</td></tr><tr><th>c</th><td>c,0</td><td>c,1</td><td>c,1</td><td>-,-</td><td>a,-</td><td>a,1</td><td>d,0</td></tr><tr><th>d</th><td>c,0</td><td>c,1</td><td>-,1</td><td>b,1</td><td>d,1</td><td>d,0</td><td>d,0</td></tr></tbody></table>
<table><caption>TABLE II</caption><thead><tr><th>CM</th><th>C<sub>i</sub></th><th>P<sub>i</sub></th></tr></thead><tbody><tr><td>1</td><td>ABDE</td><td>Ø</td></tr><tr><td>2</td><td>BCD</td><td>(AB)(AG)(DE)</td></tr><tr><td>3</td><td>CFG</td><td>(CD)(EH)</td></tr><tr><td>4</td><td>DEH</td><td>(AB)(AD)</td></tr><tr><td>5</td><td>BC</td><td>Ø</td></tr><tr><td>6</td><td>CD</td><td>(AG)(DE)</td></tr><tr><td>7</td><td>CF</td><td>(CD)</td></tr><tr><td>8</td><td>CG</td><td>(CD)(FG)</td></tr><tr><td>9</td><td>FG</td><td>(EH)</td></tr><tr><td>10</td><td>DH</td><td>Ø</td></tr><tr><td>11</td><td>AG</td><td>Ø</td></tr><tr><td>12</td><td>F</td><td>Ø</td></tr></tbody></table>

<figure><img src="image_4.png" /></figure>

Algorithme de Meisel
Exemple 9 : Exemple d'application complet.

<table><thead><tr><th></th><th>u<sub>1</sub></th><th>u<sub>2</sub></th><th>u<sub>3</sub></th><th>u<sub>4</sub></th></tr></thead><tbody><tr><td>1</td><td>-</td><td>3,1</td><td>5,1</td><td>2,1</td></tr><tr><td>2</td><td>5,0</td><td>-</td><td>-</td><td>-</td></tr><tr><td>3</td><td>6,0</td><td>6,1</td><td>-</td><td>-</td></tr><tr><td>4</td><td>-</td><td>-</td><td>2,1</td><td>-</td></tr><tr><td>5</td><td>-</td><td>6,0</td><td>1,0</td><td>4,1</td></tr><tr><td>6</td><td>3,0</td><td>-</td><td>2,0</td><td>3,1</td></tr></tbody></table>

1° Table d'implication :

<table><tbody><tr><td>2</td><td>V</td></tr><tr><td>3</td><td>36 56</td></tr><tr><td>4</td><td>25 V V</td></tr><tr><td>5</td><td>X V X X</td></tr><tr><td>6</td><td>X 35X 36V X 12 34</td></tr><tr><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr></tbody></table>

2° Compatibles maximaux (C.M.) :

1) 56

2) 34, 36, 56

3) 234, 36, 25, 56

4) 1234, 36, 25, 56 = compatibles maximaux.

3° Classes de compatibilité première :

<table><thead><tr><th>C<sub>i</sub></th><th>P<sub>i</sub></th></tr></thead><tbody><tr><td>1234</td><td>(56) (36) (25)</td></tr><tr><td>36</td><td>Ø</td></tr><tr><td>25</td><td>Ø</td></tr><tr><td>56</td><td>(12) (34)</td></tr></tbody></table>
développement :

<table><thead><tr><th>C<sub>i</sub></th><th>P<sub>i</sub></th></tr></thead><tbody><tr><td>1234</td><td>(56) (36) (25)</td></tr><tr><td>36</td><td>Ø</td></tr><tr><td>25</td><td>Ø</td></tr><tr><td>56</td><td>(12) (34)</td></tr><tr><td>123</td><td>(56) (36)</td></tr><tr><td>124</td><td>(25)</td></tr><tr><td>134</td><td>(36) (25)</td></tr><tr><td>234</td><td>56</td></tr><tr><td>12</td><td>Ø</td></tr><tr><td>13</td><td>(36)</td></tr><tr><td>24</td><td>Ø</td></tr><tr><td>34</td><td>Ø</td></tr></tbody></table>

4° Algorithme de Meisel

<table><thead><tr><th></th><th>figure</th><th></th><th>fois</th></tr></thead><tbody><tr><td>2</td><td>"</td><td>7</td><td>"</td></tr><tr><td>3</td><td>"</td><td>7</td><td>"</td></tr><tr><td>4</td><td>"</td><td>5</td><td>"</td></tr><tr><td>5</td><td>"</td><td>2</td><td>"</td></tr><tr><td>6</td><td>"</td><td>2</td><td>"</td></tr></tbody></table>

Choisissons arbitrairement le 5 : (25) (56)

(2 arbres)

<figure><img src="image_5.png" /></figure>
<figure><img src="image_6.png" /></figure>

d'où les solutions :
(25) (36) (124)
(25) (36) (134)
(56) (12) (34)
(12) (34) (56)

posons alors $A = 14 \quad B = 25 \quad C = 36$

La table devient :

<table><thead><tr><th></th><th>X1</th><th>X2</th><th>X3</th><th>X4</th></tr></thead><tbody><tr><th>A</th><td>-</td><td>C,1</td><td>B,1</td><td>B,1</td></tr><tr><th>B</th><td>B,0</td><td>C,0</td><td>A,0</td><td>A,1</td></tr><tr><th>C</th><td>C,0</td><td>C,1</td><td>B,0</td><td>C,1</td></tr></tbody></table>

## VII. PROCEDURE DE REDUCTION LIGNES-COLONNES. [4]

La méthode précédente conduit rapidement à une réduction des états de la machine. Nous nous proposons dans ce paragraphe de la réaliser, afin de réduire également le nombre des entrées, si possible.

L'idée directrice est d'utiliser **l'algorithme de Meisel** (§ 6) aménagé de manière à introduire simultanément les regroupements des entrées compatibles.

Nous nous référerons aux classes définies sur les états de la machine M en parlant de Q-classes. Les classes ci-dessous définies sur les entrées sont des U-classes.
**Définition** Une U-classe de compatibilité $E_j = \{u_{j_i}, \dots, u_{j_m}\}$ est une classe dans laquelle pour tout état $q_i$ :

a) les sorties définies sont identiques

b) les états-cibles définis forment une classe d'états compatibles (Q-classe).

**Définition** L'ensemble $R_j$ des U-classes impliquées par $E_j$ est l'ensemble des $C_{ji}$ tel que :

1) $C_{ji}$ a plus d'un élément

2) $C_{ji} \neq C_{ji'}$ si $C_{ji'} \in R_j$

La procédure proposée est présentée ci-dessous sur un exemple.

## VII. 1. Présentation de la méthode sur un exemple.

Considérons la machine décrite par la table suivante :

<table><thead><tr><th></th><th>α</th><th>β</th><th>γ</th><th>δ</th><th>Σ</th></tr></thead><tbody><tr><td>a</td><td>b, --</td><td>d, --</td><td>d, --</td><td>a, 1 -</td><td>-, --</td></tr><tr><td>b</td><td>-, --</td><td>e, 0 0</td><td>e, 0 0</td><td>b, --</td><td>b, 0 0</td></tr><tr><td>c</td><td>b, 1 1</td><td>-, --</td><td>d, --</td><td>-, --</td><td>a, --</td></tr><tr><td>d</td><td>d, --</td><td>-, -- 0</td><td>f, --</td><td>-, 0 -</td><td>-, --</td></tr><tr><td>e</td><td>f, 1 -</td><td>-, 1 0</td><td>-, 1 -</td><td>a, 0 0</td><td>c, 0 -</td></tr><tr><td>f</td><td>e, 1 -</td><td>-, 1 0</td><td>-, 1 -</td><td>-, 0 0</td><td>-, 0 -</td></tr></tbody></table>
## 1ère Etape :

Former la table d'implication des états et déterminer les C.M.

<figure><img src="image_7.png" /></figure>

Les compatibles maximum sont :

- def

- cd, def

- bcd, def

- abc, bcd, def

CM = {abc, bcd, def}

## 2ème Etape : Etablissons la table d'implication des entrées. Cette table nous donne les conditions de compatibilité entre états, requises pour que certaines entrées soient compatibles.

Regroupons ces résultats sous forme d'état (nous symbolisons les entrées par $\bar{u}_i$ = colonnes d'entrées agrégées, $\overline{J(u_i)}$ symbolisant les états (compatibles) impliqués par $\bar{u}_i$.

<figure><img src="image_8.png" /></figure>

α β γ δ

<table><thead><tr><th>$\bar{u}_i$</th><th>$\overline{J(u_i)}$</th></tr></thead><tbody><tr><td>$\delta\epsilon$</td><td>ac</td></tr><tr><td>$\beta\gamma$</td><td>-</td></tr><tr><td>$\alpha\beta$</td><td>bd</td></tr><tr><td>$\alpha\beta\gamma$</td><td>bd<br>df</td></tr></tbody></table>
Il est bien entendu qu'aucun sous-ensemble des Q-compatibles (états) précédents ne permettront le regroupement des entrées (compatibles) précisées.

Ainsi $\delta\epsilon$ est U-compatible si ac est Q-compatible, mais $\delta\epsilon$ ne peut l'être pour a ou c seul. Il convient de se souvenir qu'un état seul est un compatible par définition.

Cependant dans la recherche d'une Q-CCP (Q-classe de compatibilité première) fermée (Algorithme du § 6) on peut rencontrer des ensembles compatibles incluant les précédents (ac $\subset$ abc).

Il est nécessaire de reconnaître lesquels de ces"sur-ensembles" incluant les $\overline{J}(\overline{u}_i)$ appartiennent encore à $\overline{J}(\overline{u}_i)$. Pour cela nous examinons les sorties correspondantes d'une part de $(\delta\epsilon, ac)$ agrégé, d'autre part de $(\delta\epsilon, q_i)$ agrégé, où $q_i$ représente un état quelconque différent de a et c. Si il n'y a pas contradiction, $acq_i \subset \overline{J}(\overline{u}_i)$ et nous le faisons figurer sur la ligne $\delta\epsilon$ du tableau.

Reprenons le tableau précédent en le complétant de la manière suivante :

<table><thead><tr><th>u&#773;<sub>i</sub></th><th>J&#773;(u&#773;<sub>i</sub>)</th><th>Sortie</th><th>J&#773;(u&#773;<sub>i</sub>) (développé)</th></tr></thead><tbody><tr><td>&delta;&epsilon;</td><td>ac</td><td>1 0</td><td>ac</td></tr><tr><td>&beta;&gamma;</td><td>-</td><td></td><td>-</td></tr><tr><td>&alpha;&beta;</td><td>bd</td><td>0 0</td><td>bd, abd</td></tr><tr><td>&alpha;&beta;&gamma;</td><td>bd</td><td>0 0</td><td>bd, abd</td></tr><tr><td></td><td>et</td><td></td><td>et</td></tr><tr><td></td><td>df</td><td>1 0</td><td>df, adf, def, adef</td></tr></tbody></table>

Cette table conditionnelle nous donne en dernière colonne les Q-compatibles nécessaires à l'existence du U-compatible correspondant (1ère colonne).

Exemple

* si ac compatible $\delta\epsilon$ l'est

* $\beta\gamma$ est compatible de toutes façons

* $\alpha\beta\gamma$ est compatible si bd l'est et si df l'est
ou si bd l'est et si def l'est
etc...
**3ème Etape :** Formons la liste des compatibles premiers de la même manière qu'au § 5.

<table><thead><tr><th>C<sub>i</sub></th><th>P<sub>i</sub></th></tr></thead><tbody><tr><td>abc</td><td>de</td></tr><tr><td>bcd</td><td>def, ab</td></tr><tr><td>def</td><td>Ø</td></tr><tr><td>ac</td><td>Ø</td></tr><tr><td>bc</td><td>de, ab</td></tr><tr><td>bd</td><td>ef</td></tr><tr><td>cd</td><td>bd, df</td></tr><tr><td>b</td><td>Ø</td></tr></tbody></table>

**4ème Etape :** Nous avons maintenant les éléments nécessaires à l'application de l'algorithme final.

Celui-ci, directement dérivé de celui de Meisel, inclu des évaluations de coûts afin d'assurer la solution minimale en ligne - colonne. Le recouvrement et la fermeture sont assurés par la procédure reprise du § 6.

Nous attribuons arbitrairement un coût de 1 à chaque ligne et à chaque colonne. Une pondération des coûts ne modifirait en rien le processus.

**Présentation de l'algorithme :**

1. Le point de départ est celui de Meisel : les compatibles comprenant l'état figurant le moins souvent dans la colonne $C_i$ : (occurence minimale) (en cas d'égalité : choix arbitraire).

<table><thead><tr><th>Q</th><th></th><th>O(Q)</th></tr></thead><tbody><tr><td>a</td><td>figure</td><td>2 fois</td></tr><tr><td>b</td><td>"</td><td>5 "</td></tr><tr><td>c</td><td>"</td><td>5 "</td></tr><tr><td>d</td><td>"</td><td>4 "</td></tr><tr><td>e</td><td>"</td><td>1 "</td></tr><tr><td>f</td><td>"</td><td>1 "</td></tr></tbody></table>
Le choix se fait entre e et f. Mais ici de toute façon, la seule combinaison où ils figurent est _def_, qui sera notre point de départ (élément générateur).

A chaque étape nous figurons la QCCP suivie du $\bar{u}_i$ autorisé, si il y en a. A la QCCP on associe le n° de l'étape de l'algorithme, au $\bar{u}_i$ le nombre total d'entrées impliqué par ce regroupement.

2 - si le $P_i$ correspondant est vide ou satisfait par les précédents, choisir parmi les états restants celui qui apparaît au minimum et recommencer. S'ils y sont tous, évaluer le _coût_ : produit du numéro de l'étape par le nombre de colonnes.

**Exemple** : une des branches donne $abc ; \beta\gamma$

2 ; 4

(puisque $abc \subset \bar{\beta}(\bar{u}_i)$ $\delta\epsilon$ non agrégé).

Le coût correspondant est $8 = 2 \times 4$.

La fermeture, au sens de Meisel, nous indique que nous avons une solution Q-minimale. Elle n'est pas forcément Q-U-minimale.

Cette solution nous indique alors quel est le nombre maximal d'étapes dans l'algorithme. La table conditionnelle (p. 22) nous indique qu'au minimum nous aurons deux entrées $(\alpha\beta\gamma)$, $(\delta\epsilon)$. Donc la 4ème étape de l'algorithme donnera au mieux un coût de $8 = 4 \times 2$. Il nous suffira d'étudier 3 étapes. Si à la 3ème aucun coût n'est inférieur à 8, la première solution sera la bonne (Cette procédure assure la _minimalité_).

sinon placer dans des branches différentes toutes les Q-CCP qui satisfont les conditions $P_i$ correspondant.

**Exemple** La 2ème branche : $ac ; \beta\gamma, \delta\epsilon$

2 ; 3

$P_{ac} = \emptyset$ il reste b d'où les 5 branches de l'étape 3 (maximum).

Parmi celles-ci deux assurent la fermeture et le recouvrement :

$$ \frac{bd ; \alpha\beta\gamma ; \delta\epsilon}{3 ; 2 = 6} $$

$$ \text{et} \quad \frac{b ; \beta\gamma, \delta\epsilon}{3 ; 3 = 9} $$
la solution de coût 9 > 8 est abandonnée ; celle de coût 6 implique un maximum de $\frac{6}{2} - 1 = 3 - 1 = 2$ étapes < 3 étapes. C'est la solution minimale.

$$ \text{Nous avons donc :} \quad \begin{cases} ac, bd, def = A, B, C \\ \alpha\beta\gamma, \delta\epsilon = \alpha', \beta' \end{cases} $$

La table étudiée se réduit donc à la suivante :

<table><thead><tr><th></th><th>α'</th><th>β'</th></tr></thead><tbody><tr><th>A</th><td>B,11</td><td>A,10</td></tr><tr><th>B</th><td>C,00</td><td>B,00</td></tr><tr><th>C</th><td>C,10</td><td>A,00</td></tr></tbody></table>

en nous arrêtant à la solution de coût 8, nous aurions eu :

$$ \begin{aligned} A &= abc \\ B &= def \end{aligned} \qquad \begin{aligned} \beta' &= \beta\gamma \\ \alpha' &= \alpha \end{aligned} $$

<table><thead><tr><th></th><th>α</th><th>β'</th><th>δ</th><th>ε</th></tr></thead><tbody><tr><th>A</th><td>A,11</td><td>B,00</td><td>A,1-</td><td>A,00</td></tr><tr><th>B</th><td>B,1-</td><td>B,10</td><td>A,00</td><td>A,0-</td></tr></tbody></table>

<figure><img src="image_9.png" /></figure>

Algorithme final

le "*" indique la fermeture et le recouvrement des états.

Ceux des colonnes sont assurés par la procédure.
VIII. CONCLUSION.

Parmi les méthodes de minimisation (voir bibliographie) nous avons retenu celles qui présentent l'avantage de travailler sans retour en arrière.

La première partie, recherche des C.M., a été programmée selon la procédure d'EBERSOLE et LECOQ [10]. La suite de l'algorithme mise au point au cours de cette étude reste à réaliser, mais il est remarquable que nous disposons maintenant d'une méthode complète.
# ANNEXE

## Démonstration des théorèmes
## Preuve du théorème 1. (p. 5)

Une machine est minimale lorsque tous ses états ont une fonction différente. Minimiser M revient donc à définir des classes $C_i$ d'états équivalents et à construire $M' = (U, Q', Y, \tau', \lambda')$ avec $Q' = \{q'_i = C_i\}$, $\tau'$ et $\lambda'$ étant les restrictions à $U \times Q$ de $\tau$ et $\lambda$.

M recouvre $M'$ par définition.

Or $q = q'$ implique :

$$ \begin{array}{l} \forall \bar{u} \in U^* \quad \lambda[\tau(q, \bar{u}), u'] = \lambda(q, \bar{u} \ u') = \lambda(q, \bar{u} \ u') = \lambda[\tau(q', \bar{u}), u'] \\ u' \in U \end{array} $$

$$ \text{donc } \forall \bar{u} \in U^* \quad \tau(q, \bar{u}) = \tau(q', \bar{u}) $$

deux états équivalents vont dans des états équivalents.

Former $\{C_i\}$ équivaut donc d'après la définition à former un recouvrement fermé .

## Démonstration du théorème 2 (p. 5) [1]

Montrons pour commencer que tout sous-ensemble extrait d'une classe de compatibilité est lui-même une classe de compatibilité.

Soit $S$ l'ensemble de toutes les classes de compatibilité de $Q$. $S$ est fermé. Soit $T$ la collection de tous les sous-ensembles de ces classes, et $S \cup T$ leur réunion. Il s'agit de montrer que $S \cup T$ est fermé.

Alors (1) $\forall s \in S$ les conditions de fermeture sont satisfaites.

(2) $\forall t \in T$ alors :

1. si $q_1$ et $q_2$ appartiennent à $t$ comme $t \subset s \in S$
$$ \lambda(q_1, u_k) = \lambda(q_2, u_k) $$
(si tous deux sont définis).

2. de plus tout ensemble impliqué par $t$ est un sous-ensemble de l'ensemble impliqué par $S$ tel que $t \subset s \in S$
donc $b \in T$.

donc $S \cup T$ est fermé.
Réciproquement supposons que tout couple d'un ensemble A est compatible et montrons que A est une classe de compatibilité.

S est le même que précédemment. T est l'ensemble des A (dont les couples sont dans S). Montrons que $S \cup T$ est fermé.

C'est réalisé pour tout $s \in S$.

1. Si $t \in T$, $q_1$ et $q_2 \in t \implies (q_1, q_2) \in S : \lambda(q_1, u_k) = \lambda(q_2, u_k)$.

2. Si $t$ implique $b$, tout couple de $t$ implique un couple de $b$ ces couples étant dans $S$ donc $b \in T$.

## Démonstration du théorème 3 (p. 6) [1]

Si il n'y a pas d'ensemble X dans la chaîne générée par B, tel que $\exists k \lambda(x_1, u_k)$ et $\lambda(x_2, u_k)$ sont définis et différents $(x_1, x_2 \in X)$ alors B, avec éventuellement des états seuls, forme un ensemble fermé.

Parallèlement la condition d'implication est assurée par le procédé. Donc B est une classe de compatibilité.

Supposons maintenant que la chaîne générée par B contienne un ensemble X du type défini ci-dessus. On définit une **chaîne inverse** comme suit :

1. X appartient à la chaîne inverse

2. si Y appartient à la chaîne inverse, tous les ensembles qui impliquent Y y sont rajoutés.

La chaîne inverse ainsi générée a les deux propriétés suivantes :

1. Si X n'est pas compatible, aucun Y généré par X ne l'est.

2. Si X appartient à la chaîne générée par B, B appartient à la chaîne inverse générée par X.

Ces propriétés impliquent que B n'est pas compatible.

## Démonstration du théorème 4 (p. 12) [2]

Supposons qu'il existe un recouvrement minimal

$$ \Omega_i = \{C_{i1} \ C_{i2} \ \dots \ C_{iK}\} $$

et que $C_{ip}$ ne soit pas une classe de compatibilité première. Il existe alors $C_m$ qui exclut $C_{ip}$ et $\Omega_i^*$ obtenu en remplaçant $C_{ip}$ par $C_m$ est aussi un recouvrement minimal. Les conditions de fermeture imposées par $C_m$ sont satisfaites et celles de $C_{i1} \ \dots \ C_{ip-1} \ \dots \ C_{iK}$ ne sont pas modifiées par la substitution.
[1] PAULL, UNGER. "Minimizing the Number of States in incompletely specified sequential Switching Functions". IRE-E.C., pp. 356-367, (Sept. 1959).

[2] GRASSELLI, LUCCIO. "A Method for Minimizing the Number of internal States in incompletely specified sequential Networks". IEEE.E.C., pp. 350-359, (Juin 1965).

[3] MEISEL. "A Note on internal State-Minimization of incompletely specified sequential Networks". IEEE E.C. (Août 1967).

[4] GRASSELLI, LUCCIO. "Method for the combined Row-column reduction of Flowtables". Automatika i Telemekhanika. n° 8. pp. 100-115, (Août 1968).

[5] J. HARTMANIS, R.E. STEARNS. "Algebraic Structure theory of Sequential Machines". Prentice-Hall, (1966).

[6] M. DEPEYROT, G. MICHEL. "Réalisation des Composants en Cascade d'une machine synchrone". IA/15 (Septembre 1970).

[7] JEHUDA KELLA. "State Minimization of Incompletely Specified Sequential Machines". IEEE. E.C. Vol. C. 19, pp. 342-348. (Avril 1970).

[8] S.C. DE SARKAR, A.K. BASU, A.K. CHOUDHURY. "Simplification of Incompletely Specified Flow Tables with the Help of Prime Closed Sets". IEEE. E.C., pp. 953-956, (Octobre 1969).
[9] EBERSOLE, LECOQ. "A Computer program for Simplifying incompletely specified sequential Machines Using the Paull and Unger Technique". NASA Technical Report n° 32 - 997/J.P.L. California Institute of Technology. Pasadena. California. (Nov. 15, 1968).

[10] G. MICHEL. "Notice d'emploi du programme PAU". IP/13 (Février 1971). (Appendice ci-joint).

[11] M. DEPEYROT. "Coassignment on an LSI macromodule for diode-free read-only programming". Rapport LABORIA (à paraître).
APPENDICE

PROGRAMME

"PAU"
ORGANISATION DE L'APPENDICE

<table><thead><tr><th></th><th>page</th></tr></thead><tbody><tr><td>1 - But du programme</td><td>33</td></tr><tr><td>2 - Utilisation</td><td>33</td></tr><tr><td>3 - Présentation des données et des résultats</td><td>33</td></tr><tr><td>Listing</td><td>34</td></tr><tr><td>Sous programme P3</td><td>35</td></tr><tr><td>Sous programme P2</td><td>37</td></tr><tr><td>Programme principal P1..</td><td>39</td></tr><tr><td>Exemples</td><td>41</td></tr><tr><td>Application au paradoxe de Guinsburg [3]</td><td>45</td></tr><tr><td>Références bibliographiques...</td><td>47</td></tr></tbody></table>
1. **BUT DU PROGRAMME**

Etant donné une machine séquentielle synchrone de MEALY (Transition/Sortie) décrite par sa table de fluence, le programme fournit la liste des compatibles et des compatible maximaux.

Il constitue une première étape d'une procédure de minimisation de machines incomplètement spécifiées [1].

La méthode utilisée est celle d'EBERSOLE et LECOQ [2].

2. **UTILISATION**

Les grandeurs traitées sont des entiers (format I4).

Les dimensions maximales de la table : 10 x 10.

Les différentes cartes contrôles utilisées sont celles du 10070 IRIA. (voir listing)

La structure d'Overlay, bien qu'inutile pour le 10070, a été conservée. PAU se compose de PAU1, PAU2, PAU3 à rentrer dans l'ordre inverse de l'énumération.

Le langage est le FORTRAN IV, entrées sur cartes perforées, sorties sur imprimante.

3. **PRESENTATION DES DONNEES ET DES RESULTATS**

1ère carte deux nombres en I4. Nombre d'états, nombre d'entrées, puis une carte par ligne de la table de fluence sous forme état, sortie. Les sorties sont 0 ou 1. Le nombre -1 représente la non spécification d'un état ou d'une sortie.

La présentation des résultats est accompagnée de commentaires explicatifs suffisants.

Temps maximum 5 mn pour un 10 x 10.
10:14 JUL 07, '70 ID=0010-C00
JOB 0301,MICHEL,1
LIMIT (TIME,5)
ASSIGN M:SI,(DEVICE,S1),(FBCD)
ASSIGN F:105,(DEVICE,S1),(FBCD)
ASSIGN M:80,(FILE,PAL3),(SAVE)
FORTRAN LS,80

PAUL et UNGER

- 7/07/70
1: SUBROUTINE P3
2: DIMENSION MACOMP(20,11),ISET(50)
3: DIMENSION LOOKUP(19),INDEX(190,3)
4: COMMON M,N,ILISK,KOUNT,LOOKUP,INDEX
5: 1 FORMAT (2014)
6: 811 FORMAT (/16H MACOMP FOR KOL=, 14/ 2014)
7: 812 FORMAT (6H ERASE, 214)
8: IDISK=1
9: 7 INC = -1
10: 6 MACOMP(1,1) = 0
11: K3=1
12: KOL=1
13: IND=1
14: 10 DO 20 I=2,M
15: MACOMP(1,I)=1
16: 20 CONTINUE
17: KOUNT = 2
18: MACOMP(2,1)=1
19: 30 DO 40 I=2,M
20: IF (INC) 35,37,37
21: 37 IF (INDEX(I-1,1)) 31,999,32
22: 35 IF (INDEX(I-1,1)) 32,999,31
23: 31 MACOMP(2,I) = 1
24: DO TO 40
25: 32 MACOMP(2,I) = 0
26: 40 CONTINUE
27: DO 41 I=1,2
28: 41 PRINT 1, (MACOMP(I,J), J=1,M)
29: 60 CONTINUE
30: KOUNT= KOUNT
31: KOL = KOL + 1
32: 72 DO 100 J=1,KOUNT1
33: IF (MACOMP(J,KOL)) 999,100,73
34: 73 KOUNT = KOUNT + 1
35: IND = LOOKUP(KOL)
36: 80 DO 90 I= 1,M
37: IF (I-KOL) 83,83,81
38: 81 IND = IND + 1
39: IF (INC) 86,85,85
40: 85 IF (INDEX(IND,1)) 83,82,82
41: 86 IF (INDEX(IND,1)) 82,83,83
42: 82 MACOMP(KOUNT,I) = 0
43: DO TO 89
44: 83 MACOMP(KOUNT,I) = MACOMP(J,I)
45: 89 CONTINUE
46: 90 CONTINUE
47: MACOMP(J,KOL) = 0
48: 100 CONTINUE
49: 120 CONTINUE
50: J=1
51: 130 CONTINUE
52: 131 DO 200 JC=1,KCOUNT
53: IF (J-JC) 140,200,140
54: 140 DO 150 I=1,M
55: IF (MACOMP(J,I)-MACOMP(JC,I)) 150,150,200
56: 150 CONTINUE
57: GO TO 152
58: CONTINUE
59: J= J+1
60: GO TO 210
61: 152 KOUNT = KOUNT - 1
62: PRINT 812, KOL,J
63: IF (J-KOUNT) 160,160,60
64: 160 DO 180 JS=J,KOUNT
65: 162 DO 170 I=1,M
66: MACOMP(JS,I) = MACOMP(JS+1,I)
67: 170 CONTINUE
68: 180 CONTINUE
69: 210 CONTINUE
70: IF (J-KOUNT) 130,130,220
71: 220 IF (KOL = I + 1) 60,222,999
72: 222 IF (INC), 224,225,225
73: 224 PRINT 242
74: 242 FORMAT (20H MAXIMAL COMPATIBLES/)
75: 225 DO 250 JS = 1,KOUNT
76: I1=0
77: 230 DO 240 I=1,M
78: IF (MACOMP(JS,I)) 232,240,239
79: 232 PRINT 233,JS
80: 233 FORMAT (11H ERROR SET,, I4)
81: GO TO 250
82: 239 I1 = I1 + 1
83: 235 ISET(I1) = I.
84: 240 CONTINUE
85: IF (INC) 241,243,243
86: 243 IF (INC=11) 245,250,250
87: 245 INC = 11
88: GO TO 250
89: 241 PRINT 2,JS,(ISET(I), I=1,11)
90: 2 FORMAT (14,2H /,2014)
91: 250 CONTINUE
92: IF (INC) 255,260,260
93: 255 INC = 0
94: MACSIZ = KOUNT
95: GO TO 6
96: 260 PRINT 244, INC
97: IDISK = 0
98: KOUNT = MACSIZ
99: PRINT 1000
100: 1000 FORMAT (//,'STUP FAU4')
101: GO TO 1001
102: 999 PRINT 998
103: 998 FORMAT (10H GOOD STOP)
104: 1001 CONTINUE
105: 244 FORMAT (13H MINIMUM SIZE/14//)

106: STOP

107: END
RTRAN LS,80

1: SUBROUTINE P2

2: DIMENSION IITTAB(4,10),L00KUP(19),INDEX(190,3)

3: COMMON M,N,IDISK,JUMP,L00KUP,INDEX,NUMBER,K3,K3T,K1,K2,MUSE,ITTAB

4: C IITERATION OF IITTAB

5: PRINT 1000

6: 1000 FORMAT (//,'PAU2',//)

7: SC IDISK = 1

8: 800 FORMAT (12H STEP NUMBER, I4)

9: 802 FORMAT (14H IITTAB(K31,1)=, I4,4H K3=,I4,5H K3T=,I4,3H I=,2I4)

10: 803 FORMAT (13H INDEX(K3,1)=, 3(I4,2X), 4H K3=, I4)

11: NUMBER=090

12: K3=1

13: 806 FORMAT (14H ITTAB,RECORD, I4//)

14: K3T=1

15: MODIF =0

16: READ DISC 1,100+(40*IDISK),((ITTAB(K1,K2),K1=1,4),K2=1,N)

17: JUMP = 2

18: GO TO 800

19: 100 CONTINUE

20: IF (K3T=4) 110,110,150

21: 110 IF (INDEX(K3,1)) 130,999,112

22: 112 DO 120 I=1,N

23: IF (ITTAB(K3T,1)) 999,120,113

24: 113 K1= IITTAB(K3T,1)

25: IF (INDEX(K1,1)) 114,999,120

26: 114 INDEX(K3,1)=-1

27: MODIF = 1

28: 120 CONTINUE

29: 130 CONTINUE

30: 810 FORMAT (13H INDEX(K3,1)=, I4, 4H K3=, I4)

31: K3= K3+1

32: K3T= K3T+1

33: 132 IF (K3=MUSE) 100,100,134

34: 134 IF (MODIF) 999,135,90

35: 135 IDISK = IDISK - 1

36: JUMP = 3

37: GO TO 850

38: 136 CONTINUE

39: WRITE DISC 1,100+(40*IDISK),((ITTAB(K1,K2),K1=1,4),K2=1,N)

40: 5 FORMAT (17H COMPATIBLE PAIRS)

41: 6 FORMAT (I4,2H ,, I4)

42: MODIF = 0

43: PRINT 5

44: DO 139 I=1,MUSE

45: IF ( INDEX(I,1)) 139,999,137

46: 137 PRINT 6, INDEX(I,2), INDEX(I,3)

47: MODIF = 1

48: 139 CONTINUE

49: 141 IF (MODIF) 999,142,145

50: 142 PRINT 143

51: 143 FORMAT (30H THERE ARE NO COMPATABLE PAIRS)

52: 143 CALL P3
53: C FETCH AND RECORD IF NECESSARY

54: 150 IDISK = K3/4

55: WRITE DISC 1,100+(40*IDISK),((ITTAB(K1,K2),K1=1,4),K2=1,N)

56: IDISK=IDISK+1

57: READ DISC 1,100+(40*IDISK),((ITTAB(K1,K2),K1=1,4),K2=1,N)

58: K3T=1

59: JUMP = 4

60: GO TO 850

61: 850 NUMBER = IDISK - 1

62: PRINT 806, NUMBER

63: GO 855 L1= 1,4

64: 855 PRINT 807, (ITTAB(1,1,L2), L2=1,N)

65: 807 FORMAT (1014)

66: GO TO(999,100,136,110), JUMP

67: 999 PRINT 998

68: 998 FORMAT (10h G00F STP)

69: STOP

70: END
ASSIGN M:80,(FILE,PAC1),(SAVE)
FORTRAN LS,80

1: DIMENSION INTAB(20,10,2),ITTAB(4,10),L00KUP(19),INDEX(190,3)
2: COMMON M,N,IDISK,JUMP,L00KUP,INDEX,NUMBER,K3,K3T,K1,K2,MUSE,ITTAB
3: 807 FORMAT (1014)
4: 805 FORMAT (//10X, 14M BEGIN PHASE I/)
5: PRINT 805
6: READ(105,1)M,N
7: 1 FORMAT (2014)
8: 00 5 I=1,M
9: 5 READ(105,1)((INTAB(I,J,K),K=1,2),J=1,N)
10: 10 MUSE = (M*(M-1))/2
11: 00 11 I=1,19
12: 11 L00KUP(I) = 0000
13: IDISK=0
14: I=0002
15: 20 L00KUP(I)= L00KUP(I-1) +M-I+1
16: IF (I-M) 21,22,999
17: 21 I= I+0001
18: 00 TO 20
19: 22 00 25 I=1,MUSE
20: 25 INDEX(I,1) = 0
21: PRINT 2
22: 2 FORMAT (6H INTAB/)
23: PRINT 4, (1, I=1,N)
24: + FORMAT (32(4X,14))
25: 00 15 I=1,M
26: 15 PRINT 3, ((INTAB(I,J,K), K=1,2), J=1,N)
27: 3 FORMAT (2014)
28: J=1
29: K3=1
30: K3T=1
31: 40 K=J+1
32: C FILL IN ITTAB
33: 44 INDEX(K3,2) = 0
34: INDEX(K3,3) = K
35: 801 FORMAT (3H J=, I4, 3H K=, I4)
36: 800 FORMAT (12H STEP NUMBER, I4)
37: 45 00 65 I=1,N
38: K1= INTAB(J,I,1)
39: K2= INTAB(K,I,1)
40: C SLT POINTERS IN ROW K3
41: 50 CONTINUE
42: 56 IF (K1) 52,51,51
43: 51 IF (K2) 52,53,53
44: 52 ITTAB(K3T,1)=0
45: 00 TO 00
49: 53 IF (K1-K2) 55,52,54
54: ITTAB(K3T,1)= L00KUP(K2) + K1 - K2
58: 00 TO 00
49: 55 ITTAB(K3T,1) = L00KUP(K1) + K2 -K1
50: C CHECK OUTPUTS AND SET INDEX ACCORDING TO OUTPUT AGREEMENT
51: 60 CONTINUE
52: IF (INTAB(J,I,2)) 65,62,62
53: 62 IF (INTAB(K,1,2)) 65,63,63
54: 63 IF (INTAB(J,1,2) - INTAB(K,1,2)) 64,65,64
55: 64 INDEX(K3,1) = -1
56: 65 CONTINUE
57: IF (INDEX(K3,1)) 70,66,999
58: 66 INDEX(K3,1) = (+1)
59: C IF NECES. RECORD ITTAB ON DISK AND START NEW ITTAB TABLE
60: 70 CONTINUE
61: K3 = K3+1
62: K3T = K3T + 1
63: K=K+1
64: IF (K31-4) 85,85,75
65: 75 CONTINUE
66: IDISK=IDISK+1
67: WRITE DISC 1,100+(40*IDISK),((ITTAB(K1,K2),K1=1,4),K2=1,N)
68: JUMP =1
69: 850 NUMBER = IDISK - 1
70: PRINT 806, NUMBER
71: DB 77 L1=1,4
72: 77 PRINT 807, (ITTAB(L1,L2), L2= 1,N)
73: 806 FORMAT (14H ITTAB,RECORD,I4//)
74: K3T=1
75: 85 IF (K-(M+1)) 44,86,86
76: 86 J=J+1
77: 804 FORMAT (3H J=, I4)
78: IF (J-4) 40,87,87
79: 87 IF (K3T-1) 999,90,88
80: 88 CONTINUE
81: IDISK=IDISK+1
82: WRITE DISC 1,100+(40*IDISK),((ITTAB(K1,K2),K1=1,4),K2=1,N)
83: 90 CALL P2
84: 999 PRINT 398
85: 998 FORMAT (10H GOOD STOP)
86: STOP
87: END

OVERLAY (REF),(EF),(PAU1),(PAU2),(PAU3)),(UNSAT,(F4LIB)),(MAP),;
(NOSYSLIB)
TREE PAU1-PAU2-PAU3
RUN

EXECUTION 10:15

BEGIN PHASE 1

INTAB

<table><thead><tr><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>2</td><td>-1</td><td>3</td><td>5</td><td>-1</td><td>-1</td><td>4</td></tr><tr><td>3</td><td>0</td><td>5</td><td>8</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>4</td><td>-1</td><td>6</td><td>-1</td><td>3</td><td>-1</td><td>-1</td></tr><tr><td>5</td><td>1</td><td>8</td><td>0</td><td>-1</td><td>-1</td><td>1</td></tr><tr><td>-1</td><td>-1</td><td>6</td><td>0</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>-1</td><td>-1</td><td>-1</td><td>1</td><td>4</td><td>-1</td><td>2</td></tr></tbody></table>

ITTAB,RECORD, 0

<table><tr><td>6</td><td>11</td><td>8</td><td>0</td></tr><tr><td>7</td><td>12</td><td>8</td><td>0</td></tr><tr><td>8</td><td>0</td><td>8</td><td>3</td></tr><tr><td>0</td><td>12</td><td>0</td><td>0</td></tr></table>

ITTAB,RECORD, 1

<table><tr><td>0</td><td>0</td><td>0</td><td>7</td></tr><tr><td>10</td><td>15</td><td>0</td><td>0</td></tr><tr><td>11</td><td>14</td><td>0</td><td>0</td></tr><tr><td>0</td><td>15</td><td>0</td><td>0</td></tr></table>

ITTAB,RECORD, 2

<table><tr><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>13</td><td>12</td><td>0</td><td>0</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>0</td><td>10</td><td>0</td></tr></table>

PAU2

ITTAB,RECORD, 0

<table><tr><td>6</td><td>11</td><td>0</td><td>0</td></tr><tr><td>7</td><td>12</td><td>0</td><td>0</td></tr><tr><td>8</td><td>0</td><td>0</td><td>3</td></tr><tr><td>0</td><td>12</td><td>0</td><td>0</td></tr></table>

ITTAB,RECORD, 1

<table><tr><td>0</td><td>0</td><td>0</td><td>7</td></tr><tr><td>10</td><td>15</td><td>0</td><td>0</td></tr></table>
11 11 0 0

0 15 0 0

ITTAB,RECORD, 2

0 0 0 0

13 12 0 0

0 0 0 0

0 0 10 0

ITTAB,RECORD, 3

0 12 0 0

0 0 0 1

0 0 0 0

0 0 10 0

ITTAB,RECORD, 0

6 11 0 0

7 12 0 0

8 0 0 3

0 12 0 0

ITTAB,RECORD, 1

0 0 0 7

10 15 0 0

11 11 0 0

0 15 0 0

ITTAB,RECORD, 2

0 0 0 0

13 12 0 0

0 0 0 0

0 0 10 0

ITTAB,RECORD, 3

0 12 0 0

0 0 0 1

0 0 0 0

0 0 10 0

ITTAB,RECORD, 0

6 11 0 0

7 12 0 0

8 0 0 3

0 12 0 0

ITTAB,RECORD, 1
0 0 0 7
10 15 0 0
11 11 0 0
0 15 0 0
ITTAB,RECORD, 2

0 0 0 0
13 12 0 0
0 0 0 0
0 0 10 0
ITTAB,RECORD, 3

0 12 0 0
0 0 0 1
0 0 0 0
0 0 10 0
ITTAB,RECORD, 2

0 12 0 0
0 0 0 1
0 0 0 0
0 0 10 0

## COMPATIBLE PAIRS

1, 5
3, 4
3, 5
3, 6
4, 5
0, 1 1 1 1 1
1, 0 0 0 1 0
ERASE 3 1
ERASE 5 1
ERASE 5 3
ERASE 5 4

## MAXIMAL COMPATIBLES

1 / 2
2 / 3 6
3 / 1 5
4 / 3 4 5
0 1 1 1 1 1
1 1 1 1 0 1
ERASE 2 1
ERASE 2 1
ERASE 3 3
ERASE 4 2
ERASE 4 3
ERASE 5 1

## MINIMUM SIZE
4

STEP PAG4
*STEP* 0
RUN
EXECUTION 12:07

BEGIN PHASE 1

INTAB

1 2 3 4
-1 -1 3 1 5 1 ? 1
5 0 -1 -1 -1 -1 -1 -1
6 0 6 1 -1 -1 -1 -1
-1 -1 -1 -1 2 1 -1 -1
-1 -1 6 0 1 0 4 1
3 0 -1 -1 2 0 3 1

PAU2

COMPATIBLE PAIRS

1, 2
1, 3
1, 4
2, 3
2, 4
2, 5
3, 4
3, 6
5, 6

0 1 1 1 1 1
1 1 1 1 0 0

ERASE 2 2
ERASE 3 3
ERASE 3 4
ERASE 4 4
ERASE 4 4
ERASE 4 4
ERASE 4 4
ERASE 5 1
ERASE 5 1

MAXIMAL COMPATIBLES

1 / 3 6
2 / 1 2 3 +
3 / 5 6
4 / 2 5

0 1 1 1 1 1
1 0 0 0 1 1

ERASE 4 1
ERASE 5 3

MINIMUM SIZE

2

STOP PAU4
*STOP* 0
APPLICATION AU PARADOXE DE
GUINSBURG

RUN

EXECUTION 12:17

BEGIN PHASE 1

INTAB

<table><tr><td></td><td>1</td><td></td><td>2</td></tr><tr><td>-1</td><td>1</td><td>3</td><td>1</td></tr><tr><td>-1</td><td>2</td><td>3</td><td>2</td></tr><tr><td>5</td><td>1</td><td>1</td><td>1</td></tr><tr><td>5</td><td>2</td><td>1</td><td>2</td></tr><tr><td>4</td><td>1</td><td>1</td><td>1</td></tr></table>

PAU2

COMPATIBLE PAIRS

<table><tr><td>1</td><td>,</td><td>3</td></tr><tr><td>1</td><td>,</td><td>5</td></tr><tr><td>2</td><td>,</td><td>4</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr></table>

ERASE 3 4

ERASE 4 1

ERASE 4 2

ERASE 4 3

MAXIMAL COMPATIBLES

<table><tr><td>1</td><td>/</td><td>1</td><td>5</td></tr><tr><td>2</td><td>/</td><td>1</td><td>3</td></tr><tr><td>3</td><td>/</td><td>2</td><td>4</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td></tr></table>

ERASE 3 1

ERASE 3 2

ERASE 4 1

ERASE 4 2

MINIMUM SIZE

3

STOP PAU4

*STOP* 0
RUN

EXECUTION 17:26

BEGIN PHASE I

INTAB

<table><thead><tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><th>4</th><td>-1</td><td>-1</td><td>-1</td><td>3</td><td>2</td><td>-1</td></tr><tr><th>-1</th><td>-1</td><td>-1</td><td>-1</td><td>5</td><td>3</td><td>0</td></tr><tr><th>-1</th><td>1</td><td>3</td><td>1</td><td>6</td><td>-1</td><td>4</td><td>-1</td></tr><tr><th>1</th><td>-1</td><td>-1</td><td>-1</td><td>3</td><td>0</td><td>5</td><td>1</td></tr><tr><th>-1</th><td>-1</td><td>-1</td><td>-1</td><td>6</td><td>1</td><td>-1</td><td>0</td></tr><tr><th>2</th><td>1</td><td>4</td><td>1</td><td>-1</td><td>1</td><td>-1</td><td>0</td></tr></tbody></table>

PAU2

COMPATIBLE PAIRS

3, 5

5, 6

MAXIMAL COMPATIBLES

1 / 1

2 / 2

3 / 4

4 / 5 6

5 / 3 5

MINIMUM SIZE

5

STOP PAU4

*STOP* 0