Confluence para mostrar términos equivalentes tiene una reducción común

Question

En LEMMA 30.3.9, Pierce indica una propiedad de confluencia para $ f _ {\ _ omega} $ :

$ s \ to_ * t \ tierre s \ to_ * u \ implies \ existe V. t \ to_ * v \ land u \ to_ * v $ < / p>

Luego afirma la siguiente proposición:

$ s \ leftrightarrow_ * t \ implies \ existe u. s \ to_ * u \ land t \ to_ * u $

Sin embargo, él no usa la propiedad anterior para demostrarlo. Recuerdo que este fue el caso de otros libros en los sistemas de reescritura a plazo que leí. Sin embargo, para mí se ve muy sencillo de probar el uso de la confluencia LEMMA.

de $ s \ leftrightarrow_ * t $ uno tiene $ s \ to_ * t $ y < Span Class="Math-contenedor"> $ s \ to_ * t \ to_ * s $ por lo tanto por Confluence $ \ existe u. s \ to_ * u \ land t \ to_ * u $ .

¿Por qué este enfoque no es correcto?

Answer 1

$ s \ leftrightarrow ^ * t $ no significa que $ s \ rudowarrow ^ * t $ y $ t \ rudowarrow ^ * s $ ! Significa que hay una cadena de reducciones $ s= s_0 \ jightleftharpoons_1 s_1 \ jextleftharpoons_2 s_2 \ justoftharpoons_3 \ cdots \ jightleftharpoons_n s_n= t $ donde cada una de las $ \ RightleFtharpoons_I $ podría ser $ \ rudowarrow $ o $ \ inmediato $ . Las direcciones pueden alternar cualquier número de veces.

La propiedad de la confluencia implica genéricamente que si $ s \ leftrightarrow ^ * t $ entonces existe $ w $ < / span> de tal manera que $ s \ rudowarrow ^ * w \ itcharrow ^ * t $ , pero se necesita un poco más de trabajo para mostrarlo. Puede combinar reducciones en $ s \ leftrightarrow ^ * t $ para agrupar reducciones consecutivas en la misma dirección juntos: $ s= T_0 \ LETIRROW ^ * U_1 \ RUDARTROW ^ * T_1 \ LETIRROW ^ * U_2 \ RudoVarrow ^ * T_2 \ LETIRROW ^ * \ CDSTS \ LEEDTARROW ^ * U_N \ Rudotrow ^ * T_N= T $ . Por confluencia en $ t_ {n-1} \ inmediato ^ * u_n \ rudotrow ^ * t_n $ , existe $ v_n $ de tal manera que $ t_ {n-1} \ rudowarrow ^ * v_n \ itcharrow ^ * t_n $ . Por lo que tenemos $ t_ {n-2} \ \ _ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ rudowarrow ^ * t_ {n-1} \ t_ {n-1} \ rudowarrow ^ * v_n \ ximoparrow ^ * t_n $ .

$$ \ comienzan {matrix} & & U_1 & & & & & u_ {n-1} & & & u_n & & u_n & & u_n & & u_n & & u_n & _ * \ Swarrow & & \ Searrow ^ * & & \ CDOTS & & _ * \ Swerrow & & \ Searrow ^ * & \ * \ Swerrow & & \ Searrow ^ * & \\ T_0 & & & T_1 & & T_ {N-2} & & & T_ {N-1} & & T_ {N-1} & & & t_n \\ & & &Es & & \ color {green} {\ searrow ^ *} & & \ color {green} {_ * \ Swerrow} & \\ & & & & \ Color {Green} {V_N} & & & \\ \ End {matrix} $$

Ahora aplique la propiedad de la confluencia nuevamente a $ t_ {n-2} \ inmediato ^ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ u_ {n-1} \ rudotrow ^ * v_n $ , obteniendo < Span Class="Math-Container"> $ v_ {n-1} $ tal que $ t_ {n-2} \ rudotrow ^ * v_ {n-1} \ salteada ^ * v_n \edoparrow ^ * t_n $ . Repita hasta que obtengas $ w= v_1 $ tal que $ t_0 \ rudotrow ^ * v_1 \ itcharrow ^ * t_n $ . Formalmente, esta es una prueba por inducción sobre el número de alternas de direcciones en la cadena $ s \ leftrightarrow ^ * t $ . Confluence le permite eliminar una alternancia a la vez. En un lenguaje más colorido, la confluencia le permite "Pop un pliegue"; Cada vez que envíe un pliegue, unen dos depresiones juntas, y si sigue haciendo eso, eventualmente obtiene una sola depresión.