Acta Mathematica Academiae Seientiarum Hungarieae Tomus 21 (3--4), (1970), pp. 437--442

S U R L E S F O N C T I O N S R E C U R S I V E S P R I M I T I V E S

D E R A M I F I C A T I O N S

Par c. PAIR et A. QUERE (Nancy)

1. Introduct ion

Dans [1] Madame R. PI~TER fait l'6tude des fonctions r6cursives primitives pour un binoide libre 17" (pour la d6finition d'un binoide libre voir [1, II] ou [2]) et montre que cette 6tude se rattache ~t la th6orie g6n6rale des ensembles holomorphes libres [3]. Les fonctions de base choisies dans [1] sont:

1 - - La fonction constante A (off A d6signe la ramification vide) 2 - - Pour tout a C V la fonction f~ de deux variables d6finie par:

(V x l , x2 C 12) f . ( x ~ , x2) = x , ~ a t x 2

3 - - Le pr6dicat d'6galit& Les fonctions rdcursives primitives sont les fonctions obtenues /t partir des

fonctions de base par un nombre fini de substitutions (Substitution) et de r6cur- rences (primitive Rekursion) du type:

f ( A , u l , . . . , u , ) = g(u~,...,u,) et pour a C V :

(A) f ( f , ( x 1 , x2), u s , . . . , u,) =

= g , ( x , , x 2, u s , . . . , u , , f ( x , , u s . . . . . u , ) , f ( x 2 , u s , . . . , u,)).

Dans ce qui suit on d6montre qu'il n'est pas n6cessaire de prendre le prddicat d'6galit6 parmi les fonctions de base. On peut faire le m6me geme de d6monstration pour le cas du monoi'de libre.

2. Nota t ions

D6sormais, nous appelerons fonctions r6cursives primitives les fonctions d6duites des seules fonctions 1 et 2 par substitutions et r6currences.

Nous aurons besoin de deux ramifications particuli&es de 12; l'une, not6e 0, sera utilis6e pour repr6senter la valeur <<faux>> des pr6dicats (la valeur <<vrai>> 6tant repr6sent6e par la ramification vide A); l'autre, not6e o-, servira h introduire une <<repr6sentation parenth6s6e>r d'une ramification (paragraphe 3) et, au lieu de comparer directement deux ramifications, nous comparerons leurs repr6sentations (paragraphe 4); ao 6tant un 616ment choisi darts V, nous poserons:

a=a0 t ao , O=aot (ao-~ao) .

17", muni de la loi ~ , est un monoide; nous notons V* (resp. (VU{o-})*) le

A c t a ~Iatbema[;-ca AcadeeTliae Scierltiarltle2 Huzzgaricae ez, ~97 o

438 C. PAIR ET A. QUERE

sous-monoide de P engendr6 par V (resp. VU {f}); les 616ments de ce sous-monoide sont appel6s mots sur V (resp. ViA {a}). Un mot sur Ves t donc une suite finie d'616mems de Ve t la longueur de ce mot est le nombre d'616ments de la suite. Le signe ~ sera parfois omis lorsqu'il portera sur un mot (par exemple, on 6crira ataoa 1 au lieu de a 1 ~ao ~ a l , pour a l , ao C V).

On dit qu'un mot fi est facteur gauche (resp. facteur gauche strict) d'un mot c~ s'il existe y (resp. s'il existe 7, ? ~ A) tel que:

=37,

? est alors le quotient 5. gauche de e par ft.

3. Mot attach~ h une ramification

Une ramification peut ~tre 6crite de mani~re unique, sous forme d'une combi- naison d'616ment de Vpar t et -~ ; par exemple la ramification x de la

a l el2

~2 (2 3

Fig. i

figure 1 s'6crit: x-----alt(a 0 -~alI(a 2 ~a3) ~a2~'(al ~a l ) ,

en convenant que le signe op6ratoire ~ a priorit6 sur le signe ~ . On peut, sans cr6er d'ambiguit6, remplacer a~*(par la seule lettre a~ ~t condition

de conserver la parenth6se fermante correspondante que nous pouvons coder par o-, et remplacer de m~me les a~ qui ne pr6c~dent pas t par a~ a; de plus les -* peuvent ~tre supprim6s; ainsi ~t partir de x on obtJent le mot:

Iz(x) = aj a o f a~ a2 f a3 f f f a2 a~ ff a 1 fla.

DI~FINITION. La fonction # de ~ darts (VU { f } ) * c ~ d6finie par

,u(A) = A I~(f.(xt, Xe))=p(x~)al~(Xa)f

est r6cursive primitive; if(x) est appel6 mot attachd ~ la ramification x. Nous allons montrer que deux ramifications qui ont le marne mot attach6 sont

6gales. Pour cela 6tudions l'ensemble P des mots <<bien parenth6s6s>> dans (VU {f})*. Cet ensemble P sera d6fini err introduisant une transformation z qui associe ~ tout mot 7 de (VU {a})*, le mot <~r6duit>> obtenu en supprimant toutes les <<parenth6ses>~

Acta Mathematica Academlae Scicntiarum Hungaricae zz~ x97 o

SUR LES FONCTIONS RECURSIVES PRIMITIVES 439"

a C V et a qui se correspondent darts ~: ainsi P sera l'ensemble des mots qui sont r6ductibles au mot vide:

D~FINmON. Soft i'application ~ de (VU {cr})* darts V* U {0} d6fmie par r6cur- rence sur la longueur d'un mot ~E(VU {a})*:

(i) ~(A) = A.

(ii) VaE V ff~a) = S I t (~) = 0 ALORS 0 SINON 1 (or) a.

(iii) SI z (~) = 0 ou A ALORS z ( ~ ) = 0 ;

SIt (~) = fib (fl E V* et b E V) ALORS t (~o-) = ft.

P e s t l'ensemble z-l(A).

LEMMe 1. Quela que soient ~, f lE(VU {o'})*

(~) # 0 e t t (,8) # 0 =~ t (~13) = t ( ~ ) , ([3)

(~) = o =~ ~ ( ~ ) = O.

Ce r&ultat se d6montre par r6currence sur la longueur de ft.

LFMME 2. Le mot attachd d route ramification sur V appartient d P.

Se d6montre par r6currence sur la ramification donn6e, ~ 1'aide du lemme 1. R6ciproquement, tout mot appartenant ~t P e s t attach6 h une ramification_

sur V. Nous n'utiliserons pas ici ce r6suttat.

PROPOSITION. Deux ramifications sont dgales si, et seulement si, elles out m~me mot attaeh6.

I1 suffit de prouver que:

(vx, yc~) ~(x)=~,(y)=x:y;

proc6dons par r6currence sur la longueur de # (x):

1) Si/l(x) =# (y ) = A, alors x = y = A.

2) Supposons p(x) et #(y) diff6rents de A, alors x et y ne sont pas vides et s'6crivent:

x = x i - , - a } x 2 y = y l - - , - b } y z .

Le plus grand facteur gauche strict de #(x)=#(xl )a tz(x2)a appartenant g P e s t p(x~); en effet un facteur gauche strict plus grand que p(xa)s'6crit p(x~)a y off 7 est facteur gauche de /z(xz); d'apr6s le lemme 1 :

; (~(x~)) # o =~ ~ ~7) # o et

, (~ (x , )a~ ) = , ( ~ ( x , ) ) a , ( ~ ) = a , (~ # ~ ;

ainsi tt(x,) a 7 n'est pas darts P. De meme, le plus grand facteur gauche strict de-

Acta Matbematlcta Academiae Scient[arum Hmzg~ricae z~, z97~,

440 C. PAIR ET A. QUERE

#(y) appartenant ~t P e s t #(Yl) et doric:

/ z (x) - -p(y) entralne /~(x0=p(y 0

d'ofi a = b, /~(x2) = #(Yz)

et, par hypoth6se de rdcurrence, x ~ = y t , x2 = y z , soit finalement x = y .

4. Predicat d'6galit6

TH~OR~ME. Le prddicat d'dgalitd d~fini par:

(Vx, y C l~) eq(x, y) --- S i x =y A L O R S A SINON 0

est rdcursif primitif.

Remarquorts que toute ramification x diff6rente de A s'dcrit de fagon unique:

x = a ~ x l ~ x 2 (aEV).

Soit f~" la fonctiort de deux variables d6finie par:

( V x l , x2~r ~) f~(xl , x2)=atx~ -~x2;

on peut introduire urt nouvel op6rateur de r6currence:

f(A, ul , . . . ,ur) = g(ul, . . . ,ur) et pour aEV:

(B) f(f" (x 1 , x2) , u l , . . . , u~) =

= g , (x l , Xz, u l , . . . , u , , f ( x t , ul . . . . , u~),f(x2, u l , . . . , u,)).

LEMME 3. Soit une fonction f obtenue par une rdeurrenee de type (B) d partir des fonetions g e t g, (pour tout a ~ V) ; si g et les g, sont rdeursives primitives f l'est ,aussi.

En effet ~ une foncfiort h on peut associer ~ ddfinie par:

/~(x, u~, ..., u,) = i~(rev (x), u~, ..., u,);*

-si h est r6cursive primitive ~ l'est aussi; or, si f est ~ par une r6currence de type (B), f est obtenue par une rdcurrence de type (A), doric la fonction f = f e s t r6cursive primitive.

LEMME 4. Pour tout dldment a de VU {~} il existe une fonetion rdcursive primitive d, telle que

(VyEI 7") (Vb E VU {o-}) d,(b ~ y) = SI b =a A L O R S y S INON O.

* rev d4signe la fonction d6finie par: rev (A)= A, rev (f~(xl, x2)) = a ~ rev (x2) ~ rev (x0 (reverslerte Allee dans [I], ramification r~fldchie darts [2]).

Acta Matbemlttica Academlae Scientiarl*~m Hungaricae 2i, z97 o

SUR LES FONCTIONS RECURSIVES PRIMITIVES 441

Remarquons que la fonction de trois variables cond d6finie par

cond (xl , x 2 , xa) = S I x l = A ALORS x 2 SINON x 3

est rdcursive primitive. Les fonctions da r@ondant ~ la question sont alors d6finies par des r6currences de type (B):

1) pour aE V d . ( A ) = 0

d . ( f s pour tout bE V, diff6rent de a

da(f2(xl, x2) ) = S I x I = A ALORS x 2 SINON 0.

2) d~(A) = 0

d~(f{,(xl, x2))= 0 pour tout a E V, diff6rent de ao

d~(fs , , x2) ) = SI eqao (xl) = A ALORS x z SINON 0,

off eqao (x) est la fonction r6cursive primitive d6finie par:

eqao ( A ) = 0

eqa 0 (f ,(x 1, x 2 ) ) - 0 pour tout aE V, diff6rent de ao

eqao(f,o(x~, x2)) = x l ~ x 2 ;

c'est-~-dire que eqao (x) = A ~=~ x = ao.

LEMME 5. I1 exiSte une fonetion rdcursive primitive 6 de deux variables telle que, lorsque x et y sont clans (VU {a})*, 6(x, y) soit le quotient gt gauche de y par x si x estfacteur gauche de y e t 0 sinon.

I1 suffit de d6finir 6 par r6currence de la fagon suivante:

a(A, y ) - - y

6( f , (x , , x2), y) =da(~(xl, y)) pour aE Y, a ~ a o ,

fi(fao(X,, x2), y) = SI eqa o (Xz) = A ALORS d r (6(xl, y)) S1NON

d.o(a(x,, y)). on montre facilement que 6 Par r6currence sur la longueur de xE(VD{a})*,

satisfait/t la propri6t6 annonc6e. Finalement la fonction eq (x, y) est d6finie par:

eq (x, y) = SI ~ (/~(x),/~(y)) -~ A ALORS A SINON 0

c'est-~-dire que eq (x, y) est r4cursive primitive.

Acta ]vlat~elnatlca Academlae Scientiarltm Hlmgaricae zi~ 197o

442 C. PAIR ET A. QUERE: SUR LES FONCTIONS RECURSIVES PRIMITIVES

5. G6n6ralisation

Toute relation binaire sur V peut-~tre prolong6e en une relation s u r f ' : iI suffit de convenir que deux ramifications r et s sont en relation si les graphes ffor~ts) sous-jacents ~ r et s soar isomorphes et si les points ~correspondants~ dans ces graphes ont des ~6tiquettes)> (ou ~<couleurs>>) en relation dans V; plus pr6cis6ment:

DI~FINITION ET PROPOSITION. Soi t F un prddieat d deux variables sur V. Prolongeons F en un prddicat P sur l? en posant

P(A,A) = A

l~(fa(xl, x2), f . ,(xl , x'2)) = i ~=* F(a, a')= i et I?(x t , x l ) = i e t l~(x2, xi) = A

Le prddicat F est rdeursif primitif

I1 suffit de reprendre la d6monstration pr6c6dente err remplapant da, pour a C V, par d., r d6finie par:

d.,r(A ) = 0

d.,r(f~(x I, xz))=0 pour tout a tel que r(b, a ) = 0

d.,r(Y;(xl , x2) ) = SI x~ = A ALORS xz SINON 0

pour tout a tel que F (b, a) = A.

(Refu le 24 FOvrier 1969.)

INSTITUT UNIVERSITAIRE DE CALCUL AUTOMATIQUE~ 42~ AV. DE LA LIBt~RATION, NANCY~ FRANCE

Bibliographie

[1] R6ZSA PI~TER, Die PAIR-schen freien Binoiden als SpezialfNle der angeordneten freien holo- morphen Mengen, Aeta Math. Aead. Sci. Hung., 21 (1970), p. 297--313.

[2] C. PAm--A. QUERE, D6finition et 6rude des bilangages r6guliers (Facult6 des Sciences de Nancy, avril 1968). Information and Control 13 (1968) p. 565--593.

[3] R6ZSA P~TER, Ober die Verallgemeinerung der Theorie der reknrsiven Funktionen ftir abstrakte Mengen geeigneter Struktur als Defmitionsbereiche, Aeta Math. Aead. Sei. Hung., 12 (3---4) (1961); 13 (1--2) (1962).

Acla Matloelnatica Academiae $cientiarum Hungaricae zz, x97o