prova di confluenza per un semplice sistema di riscrittura

Question

Supponiamo di avere un linguaggio semplice che consiste di termini:

• $ \ mathtt {true} $
• $ \ mathtt {false} $
• Se $ t_1, t_2, T_3 $ sono termini allora lo è anche $ \ mathtt {if} \: T_1 \: \ mathtt {poi} \: t_2 \: \ mathtt {else} \: T_3 $

Ora assumere le seguenti regole di valutazione logica:

$$ \ begin {raccogliere *} \ Dfrac {} {\ Mathtt {if} \: \ mathtt {true} \: \ mathtt {} quindi \: t_2 \: \ mathtt {else} \: T_3 \ a t_2} \ Text {[E-IfTrue]} \ quad \ Dfrac {} {\ Mathtt {if} \: \ mathtt {false} \: \ mathtt {} quindi \: t_2 \: \ mathtt {else} \: T_3 \ a T_3} \ Text {[E-IfFalse]} \\ \ {Dfrac t_1 \ a t_1' } {\ Mathtt {if} \: T_1 \: \ mathtt {poi} \: t_2 \: \ mathtt {else} \: T_3 \ a \ mathtt {if} \: T_1' \: \ mathtt {poi} \: t_2 \: \ mathtt {else} \: T_3} \ Text {[E-Se]} \\ \ End {raccogliere *} $$

Supponiamo aggiungiamo anche la seguente regola funky:

$$ \ {Dfrac t_2 \ a t_2' } {\ Mathtt {if} \: T_1 \: \ mathtt {poi} \: t_2 \: \ mathtt {else} \: T_3 \ a \ mathtt {if} \: T_1 \: \ mathtt {poi} \: t_2' \: \ mathtt {else} \: T_3} \ Text {[E-IfFunny]} $$

Per questo semplice linguaggio con il dato di valutazione regole desidero dimostrare il seguente:

Teorema: Se $ r \ rightarrow s $ e $ r \ rightarrow t $ allora c'è qualche termine $ u $ tale che $ s \ rightarrow u $ e $ t \ rightarrow u $ .

Mi dimostrarlo per induzione sulla struttura di $ R $. Qui è la mia prova finora, è andato tutto bene, ma io sono bloccato all'ultimo caso. Sembra che l'induzione sulla struttura di $ r $ non è bastando, qualcuno può darmi una mano?

Prova Per induzione su $ R $, noi separare tutte le forme che $ r $ può assumere:.

1. $ R $ è una constante, nulla da dimostrare in quanto una forma normale non restituisce nulla.
2. $ r = $ se è vero allora $ R_2 $ altro $ r_3 $. (A) entrambe le derivazioni sono state fatte con la regola E-IfTrue. In questo caso $ s = t $, quindi non c'è nulla da dimostrare. (B) un deriviation è stato fatto con la regola di E-IfTrue, l'altro con la regola di E-divertente. Assumere $ r \ rightarrow s $ è stato fatto con E-IfTrue, l'altro caso è equivalentemente provata. Ora sappiamo che $ s = R_2 $. Sappiamo anche che $ t = $ se è vero allora $ r'_2 $ altro $ r_3 $ e che esiste una certa deriviation $ R_2 \ rightarrow r'_2 $ (premessa). Se ora scegliamo $ u = r'_2 $, concludiamo il caso.
3. $ r = $ se falsa allora $ R_2 $ altro $ r_3 $. Equivalentemente dimostrato come sopra.
4. $ r = $ se $ R_1 $ allora $ R_2 $ altro $ r_3 $ con $ R_1 \ neq $ vero o falso. (A) sia deriviations sono state fatte con la E-Se la regola. Ora sappiamo che $ s = $ se $ r'_1 $ allora $ R_2 $ altro $ r_3 $ e $ t = $ se $ r '' _ 1 $ quindi $ R_2 $ altro $ r_3 $. Sappiamo anche che esiste deriviations $ R_1 \ rightarrow r'_1 $ e $ R_1 \ rightarrow r '' _ 1 $ (i locali). Ora possiamo usare il Hypothese di induzione a dire che esiste un certo termine $ r '' '_ 1 $ tale che $ r'_1 \ rightarrow r' '' _ 1 $ e $ r '' _ 1 \ rightarrow r '' '_ 1 $. Ora concludiamo il caso dicendo $ u = $ se $ r '' '_ 1 $ quindi $ R_2 $ altro $ r_3 $ e notando che $ s \ rightarrow u $ e $ t \ rightarrow u $ da E-Se la regola. (B) una derivazione è stato fatto da E-Se regola e uno per la regola e-divertente.

Questo secondo caso, in cui una derivazione è stato fatto da E-Se e uno da E-divertente è il caso che mi manca ... io non riesco a essere in grado di utilizzare le ipotesi.

Guida sarà molto apprezzato.

Answer 1

Ok, prendiamo in considerazione il caso che $ r = \ mathtt {if} \: T_1 \: \ mathtt {poi} \: t_2 \: \ mathtt {else} \: T_3 $, $ s $ è stato derivato applicando la e-Se regola e $ t $ è stata derivata applicando la regola di e-divertente: quindi $ s = \ mathtt {if} \: t'_1 \: \ mathtt {} quindi \: t_2 \: \ mathtt {else} \: T_3 $ dove $ t_1 \ rightarrow t'_1 $ e $ t = \ mathtt {if} \: T_1 \: \ mathtt {} quindi \: t'_2 \: \ mathtt {else} \: T_3 $ dove $ t_2 \ rightarrow t'_2 $.

Il $ u $ che stiamo cercando è di $ u = \ mathtt {if} \: t'_1 \: \ mathtt {} quindi \: t'_2 \: \ mathtt {else} \: T_3 $. $ S \ rightarrow u $ risulta dalla regola di E-divertente e $ t \ rightarrow u $ risulta dalla regola di E-Se.

Answer 2

Un po 'di terminologia può aiutare se si vuole guardare questo in su: queste regole sono riscrittura regole , non hanno nulla a che fare con il tipo di systems¹. La proprietà si sta cercando di dimostrare è chiamato confluenza ; Più in particolare, si tratta di forte confluenza : se un termine può essere ridotto in modi diversi in un unico passaggio, possono convergere di nuovo al passo successivo. In generale, confluenza permette lì per essere qualsiasi numero di passaggi e non solo uno: se $ r \ a ^ * s $ e $ r \ a ^ * t $ poi c'è $ u $ tale che $ s \ a ^ * u $ e $ t \ a ^ * U $ -. se un termine può essere ridotto in modo diverso, non importa quanto lontano hanno divergevano, possono finalmente convergere di nuovo

Il modo migliore per dimostrare una proprietà di tali regole di riscrittura induttivamente definite per induzione sulla struttura della derivazione della riduzione, piuttosto che la struttura del termine ridotta. Qui, sia le opere, perché le regole seguono la struttura del termine sinistra, ma il ragionamento sulle regole è più semplice. Invece di tuffarsi nel termine, si prende tutte le coppie di regole, e vedere quale termine potrebbe essere un lato sinistro per entrambi. In questo esempio, si ottengono gli stessi casi alla fine, ma un po 'più veloce.

Nel caso in cui ti dà problemi, da un lato riduce il “se” parte e l'altro lato riduce il “poi” parte. Non c'è sovrapposizione tra le due parti che il cambiamento ($ t1 $ in [E-Se], $ t_2 $ in [E-IfFunny]), e non c'è vincolo $ t_2 $ in [E-Se] o $ t_1 $ in [E-IfFunny]. Quindi, quando si dispone di un termine di cui si applicano entrambe le regole - che deve essere della forma $ \ mathtt {if} \: R_1 \: \ mathtt {poi} \: R_2 \: \ mathtt {else} \: $ r_3, è può scegliere di applicare le regole in qualsiasi ordine:

$$ \ begin {array} {} RCL & \ Mathtt {if} \: R_1 \: \ mathtt {} quindi \: R_2 \: \ mathtt {else} \: r_3 & \\ {\ Small \ text {[E-Se]}} \ swarrow & & \ searrow {\ small \ text {[E-IfFunny]}} \\ \ Mathtt {if} \: R_1' \: \ mathtt {poi} \: R_2 \: \ mathtt {else} \: r_3 & & \ mathtt {if} \: R_1 \: \ mathtt {poi} \: R_2' \: \ mathtt {else} \: \\ r_3 {\ Small \ text {[E-IfFunny]}} \ searrow & & \ swarrow {\ small \ text {[E-Se]}} \\ & \ Mathtt {if} \: R_1' \: \ mathtt {} quindi \: R_2' \: \ mathtt {else} \: r_3 & \\ \ End {array} $$

¹ _{a volte ti vedi i tipi e di riscrittura insieme, ma al loro nucleo Sono concetti ortogonali.}