la preuve de Confluence pour un système de réécriture simple,

Question

Supposons que nous ayons un langage simple qui se compose des termes:

• $ \ mathtt {true} $
• $ \ mathtt {false} $
• si t_1 $, t_2, T_3 $ sont des termes alors est donc $ \ mathtt {if} \: t_1 \: \ mathtt {alors} \: t_2 \: \ mathtt {else} \: T_3 $

Supposons maintenant les règles d'évaluation logique suivantes:

$$ \ begin {*} rassembler \ Dfrac {}       {\ Mathtt {if} \: \ {mathtt true} \: \ {mathtt alors} \: t_2 \: \ mathtt {else} \: T_3 \ à t_2}       \ Texte {[E-ifTrue]} \ quad \ Dfrac {}       {\ Mathtt {if} \: \ {mathtt false} \: \ {mathtt alors} \: t_2 \: \ mathtt {else} \: T_3 \ à T_3}       \ Texte {[E-iffalse]} \\ \ Dfrac {t_1 \ to t_1' }       {\ Mathtt {if} \: t_1 \: \ mathtt {alors} \: t_2 \: \ mathtt {else} \: T_3 \ to \ mathtt {if} \: t_1' \: \ mathtt {alors} \: t_2 \: \ mathtt {else} \: T_3}       \ Texte {[E-Si]} \\ \ End {*} $$ rassembler

Supposons que l'on ajoute aussi la règle géniale suivante:

$$ \ Dfrac {t_2 \ to t_2' }       {\ Mathtt {if} \: t_1 \: \ mathtt {alors} \: t_2 \: \ mathtt {else} \: T_3 \ to \ mathtt {if} \: t_1 \: \ mathtt {alors} \: t_2' \: \ mathtt {else} \: T_3}       \ Texte {[E-IfFunny]} $$

Pour cette langue simple avec l'évaluation donnée des règles que je souhaite prouver les éléments suivants:

Théorème: Si $ r \ rightarrow s $ et $ r \ rightarrow t $, alors il y a un terme $ u $ tel que $ s \ rightarrow u $ et $ t \ rightarrow u $ .

Je suis prouvons par induction sur la structure de $ r $. Voici ma preuve à ce jour, tout cela a bien fonctionné, mais je suis coincé au dernier cas. Il semble que l'induction sur la structure de $ r $ est pas sufficing, quelqu'un peut-il me aider à sortir?

Preuve Par récurrence sur $ $ r, nous séparer toutes les formes que $ $ r peut prendre:.

1. $ r $ est une constante, rien à prouver car une forme normale n'évalue à rien.
2. $ r = $ si elle est vraie alors r_2 $ ELSE $ $ de r_3 de $. (A) les deux dérivations ont été faites à la règle E-ifTrue. Dans ce cas $ s = t $, donc il n'y a rien à prouver. (B) une deriviation a été fait avec la règle E-ifTrue, l'autre avec la règle E-Amusant. On suppose a été fait de $ de $ r \ rightarrow avec E-ifTrue, l'autre cas est prouvé de façon équivalente. Nous savons maintenant que $ s = r_2 $. Nous savons aussi que $ t = $ si elle est vraie alors r'_2 $ $ $ $ autre r_3 et qu'il existe un deriviation $ r_2 \ rightarrow r'_2 $ (la prémisse). Si nous choisissons maintenant $ u = r'_2 $, nous concluons le cas.
3. $ r = $ si elle est fausse alors r_2 $ $ $ autre r_3 $. Comme ci-dessus prouvé de manière équivalente.
4. $ r = $ si avec $ r_1 alors r_2 $ $ $ $ autre r_3 r_1 $ $ \ neq $ true ou false. (A) les deux deriviations ont été faites avec l'E-Si la règle. Nous savons maintenant que $ s = $ si $ r'_1 $, alors r_2 $ $ $ else r_3 $ et $ t = $ si $ r '' _ 1 $, alors $ r_2 $ d'autre r_3 de $ $. Nous savons aussi qu'il existe deriviations $ r_1 \ rightarrow r'_1 $ et $ r_1 \ rightarrow r '' _ 1 $ (les locaux). Nous pouvons maintenant utiliser l'hypothese d'induction de dire qu'il existe un terme $ r '' '_ 1 $ tel que $ r'_1 \ rightarrow r' '' _ 1 $ et $ r '' _ 1 \ rightarrow r '' '_ 1 $. Nous concluons maintenant le cas en disant $ u = $ si $ r '' '_ 1 $, alors r_2 $ $ ELSE r_3 $ $ et en remarquant que $ s \ rightarrow u $ et $ t \ rightarrow u $ par E-Si la règle. (B) une dérivation a été faite par l'E-Si la règle et un par la règle E-drôle.

Ce dernier cas, où l'on dérivation a été faite par E-Si et un par E-Funny est le cas, je suis absent ... Je ne peux pas l'air d'être en mesure d'utiliser les hypothèses.

aide sera très appréciée.

Answer 1

Ok, donc nous allons examiner le cas que $ r = \ mathtt {if} \: t_1 \: \ mathtt {alors} \: t_2 \: \ mathtt {else} \: T_3 $, $ s $ est dérivé en appliquant la règle E-Si et $ t $ a été obtenu en appliquant la règle E-Funny: donc $ s = \ mathtt {if} \: t'_1 \: \ mathtt {} alors \: t_2 \: \ mathtt {else} \: T_3 $ où $ t_1 \ rightarrow t'_1 $ et $ t = \ mathtt {if} \: t_1 \: \ mathtt {} alors \: t'_2 \: \ mathtt {else} \: T_3 $ où $ t_2 \ rightarrow t'_2 $.

$ u $ que nous recherchons est $ u = \ mathtt {if} \: t'_1 \: \ mathtt {} alors \: t'_2 \: \ mathtt {else} \: T_3 $. $ S \ rightarrow u $ découle de la règle E-Funny et $ t \ rightarrow u $ découle de la règle E-Si.

Answer 2

Une petite terminologie peut aider si vous voulez regarder ce haut: ces règles sont rewriting règles , ils ont rien à voir avec le type systems¹. La propriété que vous essayez de prouver est appelé confluent ; plus précisément, il est forte confluence : si un terme peut être réduit de différentes manières à un pas, ils peuvent converger de retour à l'étape suivante. En général, la confluence permet qu'il y ait un certain nombre d'étapes et pas seulement un: si $ r \ à ^ * s $ et $ r \ à ^ * t $, alors il y a $ u $ tel que $ s \ à ^ * u $ et t \ à ^ $ * u $ -. si un terme peut être réduite de différentes manières, peu importe dans quelle mesure ils ont divergé, ils peuvent éventuellement converger retour

La meilleure façon de prouver une propriété de ces règles de réécriture définies inductivement se fait par induction sur la structure de la dérivation de la réduction, plutôt que la structure du terme réduite. Ici, que ce soit des œuvres, car les règles suivent la structure du terme à la main gauche, mais le raisonnement sur les règles est plus simple. Au lieu de plonger dans le terme, vous prenez toutes les paires de règles, et voir ce terme pourrait être un côté gauche pour les deux. Dans cet exemple, vous obtiendrez les mêmes cas à la fin, mais un peu plus rapide.

Dans le cas qui vous donne du mal, d'un côté réduit le « si » une partie et l'autre côté réduit la partie « then ». Il n'y a pas de chevauchement entre les deux parties que le changement ($ t1 $ dans [E-Si], $ t_2 $ dans [E-IfFunny]), et il n'y a pas de contrainte sur t_2 $ $ dans [E-Si] ou $ t_1 $ dans [E-IfFunny]. Ainsi, lorsque vous avez un terme à laquelle les deux règles applicables - qui doit être de la forme $ \ mathtt {if} \: r_1 \: \ mathtt {alors} \: r_2 \: \ mathtt {else} \: r_3 $, vous peut choisir d'appliquer les règles dans un ordre quelconque:

$$ \ begin {array} {} rcl  & \ Mathtt {if} \: r_1 \: \ mathtt {} alors \: r_2 \: \ mathtt {else} \: \\ & r_3  {\ Small \ texte {[E-Si]}} \ swarrow & & \ searrow {\ small \ texte {[E-IfFunny]}} \\ \ Mathtt {if} \: r_1' \: \ mathtt {alors} \: r_2 \: \ mathtt {else} \: r_3 & & \ mathtt {if} \: r_1 \: \ mathtt {alors} \: r_2' \: \ mathtt {else} \: \\ r_3  {\ Small \ texte {[E-IfFunny]}} \ searrow & & \ swarrow {\ small \ texte {[E-Si]}} \\  & \ Mathtt {if} \: r_1' \: \ mathtt {} alors \: r_2' \: \ mathtt {else} \: \\ & r_3 \ End {array} $$

¹ _{Vous verrez parfois les types et ré-écriture ensemble, mais à leur cœur ils sont des concepts orthogonaux.}