prueba de confluencia para un sistema de reescritura sencilla

Question

Supongamos que tenemos un lenguaje simple que consta de los términos:

• $ \ mathtt {true} $
• $ \ mathtt {false} $
• Si $ t_1, t_2, t_3 $ son términos que así es $ \ mathtt {if} \: t_1 \: \ mathtt {continuación} \: t_2 \: \ mathtt {else} \: t_3 $

A continuación, suponga las siguientes reglas de evaluación lógica:

$$ \ begin {*} recopilar \ {} Dfrac {\ Mathtt {if} \: \ mathtt {true} \: \ {mathtt entonces} \: t_2 \: \ mathtt {else} \: t_3 \ a t_2} \ Text {[E-ifTrue]} \ quad \ {} Dfrac {\ Mathtt {if} \: \ mathtt {false} \: \ {mathtt entonces} \: t_2 \: \ mathtt {else} \: t_3 \ a t_3} \ Text {[E-ifFalse]} \\ \ Dfrac {t_1 \ t_1' a} {\ Mathtt {if} \: t_1 \: \ mathtt {continuación} \: t_2 \: \ mathtt {else} \: t_3 \ a \ mathtt {if} \: t_1' \: \ mathtt {continuación} \: t_2 \: \ mathtt {else} \: t_3} \ Text {[E-Si]} \\ \ End {*} $$ reunir

Supongamos que añadimos también la siguiente regla cobarde:

$$ \ Dfrac {t_2 \ t_2' a} {\ Mathtt {if} \: t_1 \: \ mathtt {continuación} \: t_2 \: \ mathtt {else} \: t_3 \ a \ mathtt {if} \: t_1 \: \ mathtt {continuación} \: t_2' \: \ mathtt {else} \: t_3} \ Text {[E-IfFunny]} $$

En este sencillo lenguaje con la evaluación dada gobierna deseo de probar lo siguiente:

Teorema: Si $ r \ rightarrow s $ y $ r \ rightarrow t $ entonces hay algún plazo $ u $ tal que $ s \ rightarrow U $ y $ t \ rightarrow U $ .

Me estoy probando esto por inducción sobre la estructura de $ R $. Aquí está mi prueba hasta el momento, todo funcionó bien, pero estoy atascado en el último caso. Parece que la inducción de la estructura de $ r $ no está bastando, ¿alguien puede ayudarme?

Prueba Por inducción sobre r $ $, vamos a separar todas las formas que $ R $ puede tomar:.

1. $ R $ es una constante, nada que probar desde una forma normal no evalúa a nada.
2. $ r = $ $ si es cierto entonces r_2 $ otro $ R_3 $. (A) ambas derivaciones se realizaron con la regla E-ifTrue. En este caso $ s = t $, por lo que no hay nada que probar. (B) un deriviation se hizo con la regla E-ifTrue, el otro con la regla E-divertido. Supongamos $ r \ rightarrow $ s se hizo con E-ifTrue, el otro caso se ha demostrado de forma equivalente. Ahora sabemos que $ s = $ r_2. También sabemos que $ t = $ $ si es cierto entonces r'_2 $ otro $ $ R_3 y que existe alguna deriviation $ r_2 \ rightarrow r'_2 $ (la premisa). Si ahora elegimos $ u = $ r'_2, llegamos a la conclusión del caso.
3. $ r = $ $ si es falso entonces r_2 $ otro $ R_3 $. De manera equivalente demostrado que el anterior.
4. $ r = $ $ si r_1 $ entonces $ $ r_2 demás R_3 $ $ $ con r_1 \ neq $ verdadera o falsa. (A) ambos deriviations se realizaron con la E-Si regla. Ahora sabemos que $ s = $ $ si r'_1 $ entonces $ r_2 otra cosa $ $ $ y $ R_3 t = $ $ si r '' _ $ 1 $ continuación r_2 $ $ demás R_3 $. También sabemos que existe deriviations $ r_1 \ rightarrow r'_1 $ y $ r_1 \ rightarrow r '' _ $ 1 (las premisas). Ahora podemos usar el hypothese inducción decir que existe algún plazo $ r '' '_ 1 $ tal que $ r'_1 \ rightarrow R' '' _ 1 $ y $ r '' _ 1 \ rightarrow r '' '_ 1 $. Ahora llegamos a la conclusión del caso diciendo $ u = $ si $ r '' '_ 1 $ entonces $ r_2 otra cosa $ $ R_3 $ y darse cuenta de que $ s \ rightarrow U $ y $ t \ rightarrow U $ por el E-Si regla. (B) una derivación fue realizada por el E-Si regla y uno por la regla E-divertido.

Este último caso, donde una derivación hecho por E-Si y uno por E-curioso es el caso que me falta ... Me parece que no puede ser capaz de utilizar las hipótesis.

ayuda será muy apreciada.

Answer 1

Muy bien, así que vamos a considerar el caso de que $ r = \ mathtt {if} \: t_1 \: \ mathtt {continuación} \: t_2 \: \ mathtt {else} \: t_3 $, $ s $ viene aplicando la regla e-Si y $ t $ se ha derivado mediante la aplicación de la regla e-divertido: Así $ s = \ mathtt {if} \: t'_1 \: \ {mathtt entonces} \: t_2 \: \ mathtt {else} \: t_3 $ donde $ t_1 \ rightarrow t'_1 $ y $ t = \ mathtt {if} \: t_1 \: \ {mathtt entonces} \: t'_2 \: \ mathtt {else} \: t_3 $ donde $ t_2 \ rightarrow $ t'_2.

El $ u $ que estamos buscando es $ u = \ mathtt {if} \: t'_1 \: \ {mathtt entonces} \: t'_2 \: \ mathtt {else} \: t_3 $. $ S \ rightarrow U $ resulta de la regla E-divertido y $ t \ rightarrow U $ resulta de la regla E-Si.

Answer 2

Un poco de terminología puede ayudar si quieres ver esto: estas reglas son reescritura reglas , no tienen nada que ver con el tipo systems¹. La propiedad que usted está tratando de probar se llama confluencia ; más específicamente, es fuerte confluencia : si un término se puede reducir de diferentes maneras en un solo paso, pueden converger hacia atrás en el siguiente paso. En general, la confluencia permite que haya ningún número de pasos y no sólo uno: si $ r \ a ^ * s $ y $ r \ a ^ * t $ entonces hay $ u $ tal que $ s \ a ^ * T $ y $ t \ a ^ * u $ -. si un término se puede reducir de manera diferente, no importa lo lejos que han divergieron, que eventualmente puede converger hacia atrás

La mejor manera de demostrar una propiedad de tales reglas de reescritura inductivamente definidos es por inducción sobre la estructura de la derivación de la reducción, en lugar de la estructura de la reducida plazo. Aquí, ya sea obras, porque las reglas siguen la estructura del término de la izquierda, pero el razonamiento de las reglas es más simple. En lugar de sumergirse en el término, se toma todos los pares de reglas, y ver lo que podría ser un término lado izquierdo para ambos. En este ejemplo, obtendrá los mismos casos en el final, pero un poco más rápido.

En el caso que le causa problemas, por un lado reduce la parte “si” y el otro lado se reduce la parte “entonces”. No hay superposición entre las dos partes de que el cambio ($ t1 $ en [E-Si], $ t_2 $ en [E-IfFunny]), y no hay ninguna restricción en $ t_2 $ en [E-Si] o en $ t_1 $ en [E-IfFunny]. Así que cuando usted tiene un término al que se aplican las dos reglas - que debe ser de la forma $ \ mathtt {if} \: r_1 \: \ mathtt {continuación} \: r_2 \: \ mathtt {else} \: $ R_3, se puede optar por aplicar las reglas en cualquier orden:

$$ \ begin {array} {} RCL Y \ mathtt {if} \: r_1 \: \ {mathtt entonces} \: r_2 \: \ mathtt {else} \: R_3 & \\ {\ Small \ text {[E-Si]}} \ swarrow & & \ searrow {\ small \ text {[E-IfFunny]}} \\ \ Mathtt {if} \: r_1' \: \ mathtt {continuación} \: r_2 \: \ mathtt {else} \: R_3 & & \ mathtt {if} \: r_1 \: \ mathtt {continuación} \: r_2' \: \ mathtt {else} \: \\ R_3 {\ Small \ text {[E-IfFunny]}} \ searrow & & \ swarrow {\ small \ text {[E-Si]}} \\ Y \ mathtt {if} \: r_1' \: \ {mathtt entonces} \: r_2' \: \ mathtt {else} \: R_3 & \\ \ End {array} $$

¹ _{A veces se verá tipos y reescritura juntos, pero en su núcleo Son conceptos ortogonales.}