La composition des opérateurs

  1. Introduction
  2. La composition parallèle
  3. La logique polonaise
  4. La logique polonaise avec numérotation des variables
    1. Généralisation, l'opérateur de composition série
    2. Généralisation aux listes
  5. La logique polonaise avec permutation-projection
    1. Généralisation aux listes
    2. Relégation des permutations-projections au rang d'opérateur avec arité d'entré et de sortie
  6. La logique polonaise avec la composition parallèle

 

1) Introduction

Considérerons un langage d'opérateurs d'arité fixé. A cette étape, un opérateur n'a pour seul fonctionnalité que de se composer avec d'autres opérateurs. Mais certain mécanisme dans la composition d'opérateurs peuvent se factoriser tel que par exemple l'application d'un même argument sur n entrés d'un opérateur n-aire, que l'on pourra écrire sans répeté n fois l'argument. On verra alors apparaître un langage plus puissant, capable d'exprimer des compositions avec un nombre de symboles beaucoup moindre.

Les fonctions s'expriment à l'aide de deux notations possibles, l'une dite fonctionnelle utilisant le symbole --> et l'autre dite évaluative utilisant le symbole = , telle que par exemple :

f : (x1,x2,x3) --> x1+x2+x3

f(x1,x2,x3) = x1+x2+x3

La tête de la fonction est constituée de la liste des arguments d'entré de la fonction. Dans l'exemple il s'agit de (x1,x2,x3). Le corps de la fonction est un programme de calcul utilisant les arguments d'entré passés à la fonction. Dans l'exemple il s'agit de x1+x2+x3. Le programme peut utiliser d'autres arguments et fonctions tel que l'opérateur + dans l'exemple. Ces variables et fonctions doivent alors être préalablement définis. L'ensemble de ces définitions préalables forme ce que l'on appel le context en cours.

f : Tête --> Corps

L'opérateur --> définie programativement la fonction. Le symbole ":" peut être remplacé par le symbole "=", un symbole d'affectation. Le symbole de la fonction f devient alors une variable libre que l'on affecte à un programme :

f = (x1,x2,x3) --> x1+x2+x3

L'opérateur de définition de fonction --> est prioritaire sur l'opérateur d'égalité =. C'est pourquoi il n'est pas necessaire d'entourer de parenthèses la définition de fonction.

2) La composition parallèle

Les combinateurs de Kleene que sont la projection et la composition parallèle, permettent de construire toutes les formes de compositions d'opérateurs d'arité fixés. On note pi,n la projection de la ième composante d'un n-uplet.

pi,n : (x1,x2,x3...,xn) --> xi

pi,n(x1,x2,x3...,xn) = xi

Utiliser n arguments n'apporte rien ici, si ce n'est une complexité d'écritre rendant quelque peu hermétique notre démonstration. Aussi nous nous contenterons d'utiliser 2 ou 3 arguments sachant que cela peut être étendu à un nombre fini quelconque d'arguments.

pi,3 : (x1,x2,x3) --> xi

pi,3(x1,x2,x3) = xi

Une liste de n éléments forme un object typé caractérisé par une arité de sortie égale à n.

 

 

On note la composition parallèle Sk,n(f,g1,g2...,gk), la composition d'un opérateur k-aire f par k opérateurs n-aire g1,g2...,gk s'aplliquant en parallèle au même n-uplet (x1,x2...,xn). Cela produit l'opérateur n-aire suivant que l'on note par abus f(g1,g2...,gk).

Sk,n(f,g1,g2...,gk) : (x1,x2...,xn) --> f(g1(x1,x2...,xn), g2(x1,x2...,xn), g3(x1,x2...,xn),.... gk(x1,x2...,xn))

Sk,n(f,g1,g2...,gk)(x1,x2...,xn) = f(g1(x1,x2...,xn), g2(x1,x2...,xn), g3(x1,x2...,xn),.... gk(x1,x2...,xn))

Sk,n(f,g1,g2...,gk) seran noté par abus par f(g1,g2...,gk).

f(g1,g2...,gk) : (x1,x2...,xn) = f(g1(x1,x2...,xn), g2(x1,x2...,xn), g3(x1,x2...,xn),.... gk(x1,x2...,xn))

f(g1,g2...,gk) (x1,x2...,xn) = f(g1(x1,x2...,xn), g2(x1,x2...,xn), g3(x1,x2...,xn),.... gk(x1,x2...,xn))

Et si on définie formellement, pour chaque valeur de n, l'opérateur --> de construction d'opérateur d'arité n+1, opérant sur les n opérateurs d'arité zéro que sont les variables muettes (x1,x2...,xn) que l'on ajoute au langage (c'est à dire à l'ensemble des opérateurs disponibles), et opérant sur un arbre clos de composition d'opérateurs, et produisant un opérateur d'arité n, alors nous pouvons écrire :

f(g1,g2...,gk) =  (x1,x2...,xn) --> f(g1(x1,x2...,xn), g2(x1,x2...,xn), g3(x1,x2...,xn),.... gk(x1,x2...,xn))

Et pour tout n-uplet (x1,x2...,xn) nous avons :

f(g1,g2...,gk) (x1,x2...,xn) = f(g1(x1,x2...,xn), g2(x1,x2...,xn), g3(x1,x2...,xn),.... gk(x1,x2...,xn))

Par exemple :

p1,3(x,y,z) = x p1,3 = (x,y,z) --> x
p3,3(x,y,z) = z p3,3 = (x,y,z) --> z
S2,3(f, p1,3, S1,3(g, p1,3)) (x,y,z) = f(z,x) S2,3(f, p1,3, S1,3(g, p1,3)) = (x,y,z) --> f(z,x)

Ce qui s'écrie plus simplement par :

f(p3,3, g(p1,3))(x,y,z) = f(z,g(x)) f(p3,3, g(p1,3)) = (x,y,z) --> f(z,g(x))

Les projections pi,n sont des opérateurs particuliers, aussi nous ne les considérerons pas comme un moyen de construction de la composition mais comme devant faire parti des opérateurs disponibles.

Seul reste la composition parallèle d'un opérateur k-aire par k opérateurs n-aire produisant un opérateur n-aire. La combinaison de plusieurs compositions parallèles forment un arbre de suites de suites, dit arbre de Kleene, ou chaque suite est composée d'opérateurs n-aire de même arité, pouvant constituer un sous-arbre de Kleene de la même façon, et où n correspond à la taille de la suite suivante au cas où celle-ci existe.

Par exemple en utilisant les notations simplifiées, soit l'opérateur K = f(g1,g2)(h1,h2), et l'opérateur g2 = p(q1,q2)(r), alors l'opérateur K peut s'écrire K = f(g1, p(q1, q2)(r))(h1, h2). La composition est associative, c'est pourquoi il n'est pas nécessaire de présiser dans quel ordre se fait la composition parallèle.

On précise l'arité des opérateurs disponibles en présentant un langage L sous une forme explicitant les arités :

L = {x, y, q1(.), q2(.), f(.,.), g1(.,.), h1(.,.), h2(.,.), p(.,.), r(.,.)}

Dans l'exemple nous avons posé : g2 = p(q1,q2)(r). Nous avons donc K = f(g1,g2)(h1,h2) = f(g1, p(q1, q2)(r))(h1, h2) :

On remarque que la notation simplifiée utilise un contexte qui est le langage L et qui apporte les informations manquantes sur l'arités des opérateurs.

On remarque également que la composition parallèle constitue une généralisation, de l'application d'un opérateur n-aire à un n-uplet d'opérateurs zéro-aire, en l'application d'un opérateur n-aire à un n-uplet d'opérateurs devant avoir tous une même arité k quelconque.

------ 21/02/2012 -------

 

2) La logique polonaise

La logique polonaise empile une suite d'opérateurs en occupant les places libres "les plus récentes". L'ajout d'un opérateur n-aire insère n nouvelles places libres. Les n places libres sont créées dans l'ordre de droite à gauche de tel sorte que la plus récente est toujours celle la plus à gauche. La logique polonaise empile ainsi des opérateurs d'arités diverses tant qu'il y a des places libres et se termine lorsqu'il n'y a plus de place libre. On dit alors que le message est clos, ou que la composition est close.

L = {a, s(.),f(.,.)}

Message clos
Formule
a
a
sa
s(a)
faa
f(a,a)
fsaa
f(s(a),a)
ffaaa
f(f(a,a),a)

Pour intégrer dans cette logique polonaise la possibilité de calculer non pas de simples éléments mais d'autres opérateurs il faut pouvoir spécifier les variables d'un nouvel opérateur en construction, ou bien pouvoir permuter et projeter les variables d'un opérateur n-aire.

3) La logique polonaise avec numérotation des variables

On introduit n meta-opérateurs zéro-aire que sont les numéros des variables 1,2,3..n, et qui permettent de désigner les places libres bloquées d'un opérateur n-aire en construction, simplement en les numérotant.

La logique polonaise avec numérotation des variables, empile ainsi des opérateurs d'arités diverses tant qu'il y a des places libres et se termine lorsqu'il n'y a plus de place libre. On dit alors que le message est meta-clos, ou que la composition est meta-close. Le résultat définie un nouvelle opérateur qui possède une arité égale au plus grand numéro utilisé.

Un opérateur tel que par exemple (x,y,z)-->f(x,y,z) sera noté par la formule f(1,2,3).

Voici quelques exemples à partir d'un langage L :

L = {a, s(.),f(.,.)}

Message clos
Formule
Opérateur
Arité
a
a
a
0
1
1
x --> x
1
2
2
(x,y) --> y
2
s1
s(1)
x --> s(x)
1
s2
s(2)
(x,y) --> s(y)
2
f11
f(1,1)
x --> f(x,x)
1
f1a
f(1,a)
x --> f(x,a)
1
f2a
f(2,a)
(x,y) --> f(y,a)
2
ff1a1
f(f(1,a),1)
x --> f(f(x,a),x)
1

Le message meta-clos peut être perçu comme un programme. Il constitue un nouvel opérateur qui peut alors être composé comme les autres opérateurs. Lorsque l'on compose de tels programmes les un à la suite des autres de la même façon que l'on empile des opérateurs, on peut les fusionner en un seul programme en effectuant le liens des variables spécifiées dans chacun des programmes. La fusion se ramène aux règles suivantes de simplification du message :

Tout d'abord on insère les symbôles | de fin de programme entre chaque message meta-clos.

  1. Lorsque le symbole | est suivi d'un opérateur n-aire x. L'opérateur x est déplacé à la première place libre numéro i du programme de gauche, et on insert juste après les variables i+0,i+1...,i+n-1 et les autres numéros >i du programme de gauche sont augmentés de (n-1).
  2. Lorsque le symbole | est suivi d'une variable numéroté j. La variable numéroté j est déplacé dans une mémoire de la première place libre numéro i du programme de gauche. La place numéro i passe ainsi à l'état occupé et possède en mémoire le numéro j.
  3. Lorsque le symbole | est suivi d'un autre symbole | ou de rien, Il faut le supprimer et effectuer dans le programme de gauche la permutation-projection mémorisée dans les variables : Les variables non occupées sont augmentées du numéro max mémorisé moins le nombre de variables occupées. Les variables occupées sont remplacées par leur numéro mémorisé.

Voici quelques exemples de fusion :

L = {a, b, c, s(.),f(.,.)}

Succession de programmes
Succession de programmes avec séparateur |
Succession de formules avec séparateur °
Programme fusionné
Formule fusionnée
s1a
s1|a
s(1) ° a
sa
s(a)
s1s1
s1|s1
s(1) ° s(1)
ss1
s(s(1))
s12
s1|2
s(1) ° 2
s2
s(2)
2a
2|a
2 ° a
1
1
2ab
2|a|b
2 ° a ° b
b
b
2s1a
2|s1|a
2 ° s(1) ° a
1
1
22
2|2
2 ° 2
3
3
2s(2)aab
2|s(2)|a|a|b
2 ° s(2) ° a ° a ° b
b
b
f1f23a
f1f23|a
f(1,f(2,3)) ° a
faf12
f(a,f(1,2))
f1f23ab
f1f23|a|b
f(1,f(2,3)) ° a ° b
fafb1
f(a,f(a,1))
f1f23abc
f1f23|a|b|c
f(1,f(2,3)) ° a ° b ° c
fafbc
f(a,f(a,c))
f21s1a
f21|s1|a
f(2,1) ° s(1) ° a
f1sa
f(1,s(a))
f21s1s1
f21|s1|s1
f(2,1) ° s(1) ° s(1)
fs2s1
f(2,s(s(1)))
f1f23s1
f1f23|s1
f(1,f(2,3)) ° s(1)
fs1f23
f(s(1),f(2,3))
f1f23s4
f1f23|s4
f(1,f(2,3)) ° s(4)
fs4f56
f(s(4),f(5,6))
f1f23f12
f1f23|f12
f(1,f(2,3)) ° f(1,2)
ff12f34
f(f(1,2),f(3,4))

Pour des raisons de lisibilité on notera le programme par sa formule, c'est à dire en ajoutant les parenthèses selon l'arité des opérateurs. Nous avons s(1) = s. Mais s ne constitue pas un programme car il n'est pas meta-clos. Si on remplaçe s(1) par s dans les successions close de programmes, on obtient une succession close de programmes plus simples et de même résultat. De même f(1,2) = f, et nous pouvons le remplacer dans les successions close de programmes.

3.1) Généralisation, l'opérateur de composition série

On peut généraliser et considérer les programmes non meta-clos en les cloturants par défaut. Les formules non-meta close sont représentés avec des points pour désigner les place libres qui n'ont pas été affectées et qui sont toujours regroupé à la fin de la formule. Par exemple la formule f(f(a,.),.) contient deux places libres.

Il y a qu'une seule possibilités de cloture par défaut, qui respecte la logique polonaise. On cloture par des variables libres supplémentaires ayant des numéros succédant le plus grand numéro déja utilisé. Ainsi f=f(1,2), s=s(1), f(a,.)=f(a,1), f(3,.)=f(3,4) etc...Ainsi en remplaçant le message non meta-clos f1f par f1f23, le message f1faaa est bien égale au message f1f23aaa. Se pose alors la question de la fin de programme. Un programme f1f23 peut être considéré comme f1|f2|3 et le résultat en est complètement changé :

f1f23 = (x,y,z)-->f(x,f(y,z))
f1|f2|3 = f12|f23|3 = (x,y,z,t,u,v)-->f(f(t,u),v)

Pour lever cette ambiguité, on est donc obligé de formaliser la fin de programme par le meta opérateur |.

On remarque alors que l'opérateur |, noté également ° dans l'espace des formules, est un opérateur associatif qui définie d'une manière trés générale l'opération de composition série de deux opérateurs. On peut ainsi composer les opérateurs en une liste. Par exemple

f ° s ° f = f|s|f = f12|s1|f12 = f(s(f(1,2)),3).

Sémentiquement, ° désigne la composition série de deux opérateurs, et | désigne la succession série de deux programmes.

3.2) Généralisation aux listes

On peut vouloir s'intéresser aux listes. En enlevant la règle d'arret des messages lorsque il n'y a plus de place libre, on crée des messages qui désignent des listes. Ainsi le programme aaaa désigne la liste (a,a,a,a) qui constitue un opétateur d'arité d'entré égale à zéro (c'est une constante) et d'arité de sortie égale à 4 (c'est un quadruplet).

Voici quelques exemples de programme d'opérateur ayant une arié d'entré et une arité de sortie :

L = {a, s(.),f(.,.)}

Programme
Formule
Opérateur
Arité
d'entré
Arité
de sortie
aaa
(a,a,a)
(a,a,a)
0
3
f2a
f(2,a)
(x,y)-->f(y,a)
2
1
af
(a,f(1,2))
(x,y)-->(a,f(x,y))
2
2
21
(2,1)
(x,y)-->(y,x)
2
2
a1
(a,1)
x-->(a,x)
1
2
f12f11
(f(1,2),f(1,1))
(x,y)-->(f(x,y),f(x,x))
2
2

Notez qu'il s'agit d'énumération plus tôt que de liste. En effet on ne peut pas définir avec ce moyen de liste de liste. Les listes sont concaténées en une seul liste, c'est pourquoi on les appellera énumérations séparées par des virgules et ne permettant pas un emboitement de parenthèses.

Jusqu'à présent les opérateurs du langage ont une arité de sortie égale à 1. On pourrait augmenter notre langage en ajoutant des opérateurs ayant une arité de sortie superieur à 1, mais cela n'apporte rien puisque l'on peut toujours remplacer un tel opérateur par ses composantes. C'est pourquoi il ne semble pas utile de considérer dans le langage des opérateurs d'arité de sortie autre que 1.

4) La logique polonaise avec permutations-projections

On introduit le meta-opérateur "." pour désigner les variables devant rester libres. Et on introduit les meta-opérateurs permutations-projections µ. Pour n = 2, il existe 3 permutations-projections. Et pour n = 3, il existe 13 permutations-projections :

n = 2
µ00
x-->(x,x)
µ01
(x,y)-->(x,y)
µ10
(x,y)-->(y,x)
n = 3
µ000
x-->(x,x,x)
µ001
(x,y)-->(x,x,y)
µ010
(x,y)-->(x,y,x)
µ100
(x,y)-->(y,x,x)
µ011
(x,y)-->(x,y,y)
µ101
(x,y)-->(y,x,y)
µ110
(x,y)-->(y,y,x)
µ012
(x,y,z)-->(x,y,z)
µ120
(x,y,z)-->(y,z,x)
µ201
(x,y,z)-->(z,x,y)
µ021
(x,y,z)-->(x,z,y)
µ210
(x,y,z)-->(z,y,x)
µ102
(x,y,z)-->(y,x,z)

Pour n = 4, il y a à peu près une soixantaine de permutations-projections.

La logique polonaise empile les opérateurs d'arités diverses ou l'opérateur "." qui occupe une place libre, tant qu'il y a des places libres et se termine lorsqu'il n'y a plus de place libre. On dit alors que le message est meta-clos, ou que la composition est meta-close. Et on peut ajouter à la fin du programme une permutation-projection qui possède une arité de sortie égale au nombre d'opérateur "." contenue dans le message.

Le programme ainsi terminé définie un nouvelle opérateur qui possède une arité égale à l'arité de l'opérateur permutation-projection si celui-ci est présent sinon possdède une arité égale au nombre d'opérateur "." figurant dans le message meta-clos.

Voici quelques exemples à partir d'un langage L :

L = {a, s(.),f(.,.)}

Message meta-clos
Formule
Opérateur
Arité
.
1
x-->x
1
s.
s(1)
x-->s(x)
1
f..
f(1,2)
(x,y)-->f(x,y)
2
f..µ00
f(1,1)
x-->f(x,x)
1
f.f..µ100
f(2,f(1,1))
(x,y)-->f(y,f(x,x))
2

4.1) Généralisation aux listes

De même, on peut généraliser aux listes. On doit formaliser la composition série de deux programmes par un meta-opérateur. L'opérateur permutation-projection joue ce rôle. Il faut donc systématiquement le mettre pour séparer deux programmes consécutifs. Pour les permutations identités, on utilisera un opérateur | plus générale qui nous évitera à devoir préciser l'arité.

Le programme définie un nouvel opérateur qui possède une arité d'entrée égale à l'arité d'entré de l'opérateur permutation-projection, et possède une arité de sortie égale à la taille de la liste produite par le programme. Voici quelques exemples :

L = {a, s(.),f(.,.)}

Message meta-clos
Formule
Opérateur
Arité d'entré
Arité
de sortie
..
(1,2)
(x,y)-->(x,y)
2
2
s..
(s(1),2)
(x,y)-->(s(x),y)
2
2
s..µ00
(s(1),1)
x-->(s(x),x)
1
2
.fa.µ01
(2,f(a,1))
(x,y)-->(y,f(a,x))
2
2
...µ000
(1,1,1)
x-->(x,x,x)
1
3

Nous introduisons de la même façon que précédement les opérateurs possédant une aritée de sortie supérieure à 1.

4.2) Relégation des permutations-projections au rang d'opérateur avec arité d'entré et de sortie.

Les meta-opérateurs permutations-projections peuvent déja être présent dans le langage L. Et plus précisement le langage L peut contenir un petit nombre de permutations-projections générant toutes les autres permutations-projections. Auquel cas, il n'est pas utile d'introduire dans le mécanisme de construction ces permutations-projections. Seul reste la composition série d'opérateur noté ° ou |, et l'évaluation des opérateurs évaluables tel que nos permutations-projections qui sont reléguées au rang de simple opérateur évaluable.

5) La logique polonaise avec la composition parallèle

On reprend l'idée de Kleen de composition parallèle et on applique une logique polonaise par dessus. On recherche un meta-opérateur qui doit nous permettre d'exprimer les arbres de suite de suite de Kleen sous forme d'un empilement. On utilise le symbôle de composition parallèle ° et un niveau de parenthèse pour chaque suite de suite de Kleen.

Les suite d'opérateurs d'arité diverse sont considéré comme des suite d'arité égale à l'arité maximale, et les opérateurs d'arité plus petite sont atteint par projection. La composition d'un opérateur d'arité n par une liste possèdant moins de n éléments et complété, on ajoute à la liste autant de fois que nécessaire le dernier élément de la liste. La composition d'un opérateur d'arité n par une liste possèdant plus de n éléments et scindée, on prend les n premier élément de la liste pour les combiner avec l'opérateur et on ajoute les éléments suivants dans une nouvelle liste avec le résultat de l'opérateur comme premier élément.

Par exemple :

L = {a, u(.), v(.), w(.), s(.), f(.,.), g(.,.), h(.,.)}

Message
Formule avec composition parallèle
Formule avec
composition série
Arité
u
u
u(1)
1
uu
(u,u)
u(1),u(1)
1
u°u
u(u)
u(u(1))
1
uu°u
(u,u)(u)
u(u(1)),u(u(1))
1
u°uu
(u(u),u)
u(u(1)),u(1)
1
ug
(u,g)
u(1),g(1,2)
2
u°g
u(g)
u(g(1,2))
2
u°gv
(u(g),v)
u(g(1,2)),v(1)
2
u°gf
(u(g),f)
u(g(1,2)),f(1,2)
2
gu
(g,u)
g(1,2),u(1)
2
g°u = g°uu
g(u,u)
g(u(1),u(1))
1
g°f = g°ff
g(f,f)
g(f(1,2),f(1,2))
2
g°uv
g(u,v)
g(u(1),v(1))
1
g°fu
g(f,u)
g(f(1,2),u(1))
2
g°f(u°g)
g(f,u(g))
g(f(1,2),u(g(1,2)))
2
g°fu°g = g°fu°gg
g(f,u)(g,g)
g(f(g(1,2),g(1,2)),u(g(1,2)))
2

Les projections pin : (x1,x2,x3...,xn)-->xi doivent appartenir aux opérateurs mis à disposition.

Comme il existe encore un jeux de parenthèses, nous n'avons pas encore une logque polonaise. Le jeux de parenthèse ne doit pas mettre en oeuvre un mécanisme de liste de liste mais doit permettre une simple énumération, c'est pourquoi l'ajout d'une liste dans une liste constitue une nouvelle liste concatènant les deux liste et non pas une liste contenant une liste :

Message
Formule avec composition parallèle
uv(wu(vw)) (u,v,w,u,v,w)
f(u(vw)) (f(u,v),w)

Dans l'exemple suivant :

Message
Formule avec composition parallèle
g°f(u°vv) g(f,u(v),v)
g°fu°vv g(f,u)(v,v)

on remarque que le niveau de parenthèse ne modifie que le sense de l'opérateur ° placé dans ce niveau de parenthèse. On peut généraliser cette propriétés. Chaque niveau de parenthèse ouvre une suite de suite de Kleen et l'opérateur ° se décline dans cette suite de suite de Kleen. On numérote les opérateurs ° selon leur niveau de parenthèse ou il se situent. Dés lors en autorisant seulement l'incrémentation d'un ou une diminution quelconque du numéro de l'opérateur ° suivant dans le message, on peut supprimer les parenthèses qui n'apportent aucune informations supplémentaires. Par convention on commence par le numéro 0. Les numéros doivent être >= 0 et peuvent augmenter d'un ou diminuer de façon quelconque lorsque l'on passe d'un opérateur ° au suivant dans le message. Par exemple :

Message
Formule avec composition parallèle
f0g1uvw0u f(g(u,v),w)(u)
u0g1uv1w u(g(u,v)(w))
u0v1w u(v(w))
u0v0w u(v)(w)
u0f1vw2u0v u(f(v,w(u)))(v)

Le codage reste complexe et ne permet pas de construire des algorithmes de balayage simple. En conclusion nous choisirons une méthode de construction progressive arité par arité de tous les opérateurs par composition parallèle.

6) Le codage des compositions parallèles

A partir d'un langage tel que L = {a,s(.),f(.,.)}, nous voulons balayer l'ensemble de tous les arbres de suites de suites de Kleen. Et nous allons le faire étape par étape, c'est à dire en partant de l'ensemble A = {a,r,f} des opérateurs élémentaires et en ajoutant toutes les opérateurs constructibles par une composition parrallèle. Dans l'exemple, il y a 6 compositions parallèles possibles :

Formule avec composition parallèle
Arité
s(a)
0
s(s)
1
s(f)
2
f(a,a)
0
f(s,s)
1
f(f,f)
2

On donne un nom à ces nouveaux opérateurs : b = s(a), u = s(s), g = s(f), c = f(a,a), v = f(s,s), h = f(f,f). Le langage est alors plus riche :

{a,b,c,s(.),u(.),v(.),f(.,.),g(.,.),h(.,.)}

Et nous recommençons à balayer l'ensemble des compositions parallèles possibles. Mais nous ne souhaitons pas recalculer ce qui à déja été fait. Pour cela il faut considérer n listes d'opérateurs de même arité, avec n pointeurs pour chaque opérateur d'arité supérieur à 0. Dans l'exemple il y a trois listes d'opérateurs :

L0 = [a]
L1 = [s] et p0_s pointe sur a, et p1_s pointe sur s, et p2_s pointe sur f
L2 = [f] et p1_f pointe sur a, et p1_f pointe sur f, et p2_f pointe sur f

Nous prenons l'opérateur s et nous l'appliquons à l'opérateur a, puis à l'opérateur s puis à l'opérateur f :

L0 = [a, s(a)]
L1 = [s, s(s)] et p0_s pointe sur s(a), et p1_s pointe sur s(s), et p2_s pointe sur s(f )
L2 = [f, s(f)] et p0_f pointe sur a, et p1_f pointe sur s, et p2_f pointe sur f

Nous prenons l'opérateur f et nous l'appliquons à l'opérateur a et s(a), puis à l'opérateur s et s(s) puis à l'opérateur f et s(f) :

L0 = [a, s(a), f(a,a), f(a,s(a)), f(s(a),a), f(s(a),s(a))]
L1 = [s, s(s), f(s,s), f(s,s(s)), f(s(s),s), f(s(s),s(s))] et p0_s pointe sur s(s) et p1_s pointe sur s(s), et p2_s pointe sur s(f )
L2 = [f, s(f), f(f,f), f(f,s(f)), f(s(f),f), f(s(f),s(f))] et p0_f pointe sur f(a,a), et p_f pointe sur f(s,s), et p2_f pointe sur f(f,f)

Nous prenons l'opérateur s et nous l'appliquons aux opérateurs s(a),...,f(s(a),s(a)), puis aux opérateurs s(s),...,f(s(s),s(s)), puis aux opérateurs s(f),...,f(s(f),s(f)) :

L0 = [a, s(a), f(a,a), f(a,s(a)), f(s(a),a), f(s(a),s(a)),s]
L1 = [s, s(s), f(s,s), f(s,s(s)), f(s(s),s), f(s(s),s(s))] et p0_s pointe sur s(s) et p1_s pointe sur s(s), et p2_s pointe sur s(f )
L2 = [f, s(f), f(f,f), f(f,s(f)), f(s(f),f), f(s(f),s(f))] et p0_f pointe sur f(a,a), et p_f pointe sur f(s,s), et p2_f pointe sur f(f,f)