Systeme de transition sur les ordre Partiellement complet

2.1.3 Quelques exemples et contre exemples de systèmes de

transition.

1) Tout opc est un s_ystème de transition de structure de transition s S //s' si et seulement si s = s'.

2) Sur l'opc N, (N, N x N) n'est pas un s_ystème de transition.

3)

,

₇₇ z ^qq hh

%%

x 3₃ y

_ee

Sur A l'opc représenté par :

les dia_grammes ci-dessous sont des s_ystèmes de transition à support A :

// y

x

S

££

--

_FF°

° ° °

S °

° ° ° ° ° °

²² ° °

z

_XX00dd

⁰⁰0₀₀S

₀₀

S 000

ÁÁ 0

yy

S

%%

x _ll

²²

_{FF° OO}

°

° °

S ° °

° °

° ° S

° ° °

--

z

££

_{__}^????_??S

??????

S ???

S ?

// %%

,, y S

_ii

[[

S

yy

\\

S

[[

S

_BB

4) Soit A un opc. Soit a0 fixé dans A. On montre sans peine _que a0 ?= {x, a0 = x} est un sous opc de A et a0 ? xa0 ? est un s_ystème de transition sur a0 ?.

2.1.4 Morphismes de systèmes de transition.

Dans le cas des s_ystèmes de transition ensemblistes, J.J.J.Rutten appelle morphisme du s_ystème de transition S vers le s_ystème de transition U toute application f : S -? U vérifiant :

i) Pour tout s, s' E S, si s S //s' alors f (s, ) S // f (s', ) (l'on dit dans ce cas _que f
préserve les transitions de S).

ii) PourtoutsESetuEU,sif(s,) S//ualorsilexistes'EStelques S // s'et
f (s') = u. (l'on dit dans ce cas _que f réfléchit les transitions de U).

En nous inspirant de cette définition, nous proposons la définition suivante de morphisme de s_ystèmes de transition sur un opc.

Définition 2.3. Soient S et U deux s_ystèmes de transition. Un morphisme de S vers U est un morphisme d'ope^s f : S -? U vérifiant :

i) Pour tout s, s' E S, si s _S> s' alors f (s)

S > f (s') ;

ii)Pour tout s E S et u E U, si f (s) _S> u alors il existe s' E S tel _que s _S> s' et

f (s') = u.

Les morphismes de s_ystèmes de transition sur des opcⁿ sont donc les applications continues _qui préservent et réfléchissent les transitions

2.1.5 Quelques propriétés des morphismes de systèmes de tran-

sition.

Au chapitre précédent, nous avons montré _que les monos (respectivement épis) de la caté_gorie CPO sont exactement des injections (respectivement surjections) continues. De ces résultats, nous déduisons les caractérisations suivantes des morphismes de s_ystèmes de transition :

Lemme 2.1. Soient S et U deux s_ystèmes de transition déterministes. Une application continue f : S -? U est un morphisme de s_ystèmes de transition si et seulement si elle préserve les transitions.

Preuve. ?) Supposons f : S -? U continue et préservent les transitions. Pour montrer _que f est un morphisme, il suffit de montrer _que f réfléchit les transitions.

Supposons _que f (s ) _S> u, alors S étant déterministe, il existe un uni_que s' E S tel _que

s _S> s'. Comme f préserve les transitions, f (s) _S> f (s' ) . Comme U est déterministe,

f (s) _S> f (s' ) et f (s ) S //u impli_quent u = f (s') . Donc f réfléchit les transitions.
)La récipro_que est immédiate.

Proposition 2.3. Tout homomorphisme de s_ystèmes de transition _qui est un homéomorphisme est nécessairement un isomorphisme.

Preuve. Soit f : S -? U un homéomorphisme. Soit g : U-? S sa bijection récipro_que. Pour montrer _que f est un isomorphisme il suffit de montrer _que g est un morphisme de s_ystèmes de transition.

· Soient u, u' E U tels _que u _S> u', alors u = f o g (u) _S> u'. Comme f réfléchit les

transitions, il existe s dans S tel _que f (s) = u' et g (u) _S> s. Or f o g (u') = u' = f (s) .

Donc g (u') = s. Partant, g (u) _S> s = g (u') . ie ; g (u) _S> g (u') .

·
· Soient u E U et s E S tels _que g (u) _S> s'. Alors g (u) _S> g o f (s') . Donc il existe

u' := f (s') tel _que g (u) = s'. Comme f préserve les transitions g (u) _S> go f (s') impli_que

fog(u) _S> fogof(s'). i.e, u _S> f(s')etgof(s')=s'

Le résultat suivant nous permet de construire des morphismes de s_ystème de transition à partir des morphismes d'opcⁿ et d'autres morphismes de s_ystèmes de transition.

Lemme 2.2. Soient S, T et U trois s_ystèmes de transition. Soient f : S -? T, g : S -? U

et h :U-? T trois applications continues rendant commutatif le dia_gramme suivant :

S	f	> T

⁰⁰⁰0₀₀₀

g 00000»0»

_FF° ° ° ° ° ° °

h

° ° ° °

° °

U

1) Si g est un épi d'opc', f et g des homomorphismes de s_ystèmes de transition, alors h est un homomorphisme de s_ystèmes de transition.

2) Si h est un mono d'opc', f et h des homomorphismes de s_ystèmes de transition, alors g est homomorphisme de s_ystème de transition.

Preuve.

Cette preuve fait usa_ge exceptionnel des relations. Contrairement à celle de J.J.J.Rutten _qui est basée sur le point de vue fonctoriel des s_ystèmes de transition ensemblistes.

1) Supposons f = h o g et g épis d'opc', f et g des homomorphismes.

· Montrons _que h préserve les transitions.

Soit u, u' E U, tels _que u S > u'. Il faut montrer _que h (u) _S> h (u') . Comme g est

un épi d'opc', il est surjectif. Il existe donc s', s E S tels _que u = g (s) et u' = g (s') .
Donc u _S> u' impli_que g (s) _S> g (s') . Comme g réfléchit les transitions, il existe

s» E S tel _que g (s») = g (s') et s _S> s». Comme f préserve les transitions,

s _S //s» implique f (s) _S> f (s»)

implique h (g (s)) _S> h (g (s'))

implique h (u) _S> h (u') .

·
· Montrons _que h réfléchit les transitions. Soit u E U et t E T tels _que h (u) _S> t.

Il faut chercher u' E U tel _que h (u') = t. g étant surjective, il existe s E S tel _que
u = g (s) . Donc h (g (u)) _S> t c-à-d f (u) _S> t. Comme f réfléchit les transitions,

f (u) S > t impli_que _qu'il existe s' E S tel _que f (s') = t et s S > s'. Or f (s') = t

é_quivaut à h (g (s')) = t. On pose u' = g (s') et on obtient u = g (s) S > g (s') = u'.

2) De fa_çon analo_gue, on montre le 2).