Confluência para mostrar termos equivalentes têm uma redução comum

Question

no lema 30.3.9, perfure afirma uma propriedade de confluência para $ f _ {\ Ômega} $ :

.

$ s \ to_ * t \ terra s \ to_ * u \ implica \ existe v. t \ to_ * v \ land u \ to_ * v $ < / p >.

Ele então afirma a seguinte proposição:

.

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

No entanto, ele não usa a propriedade acima para provar isso. Eu lembro que este foi o caso de outros livros sobre sistemas de reescrita a termo que eu li. No entanto, para mim parece muito simples provar usando o lema de confluência.

de $ s \ leftrightarrow_ * t $ um tem $ s \ to_ * t $ e < span class="contentor de matemática"> $ s \ to_ * t \ to_ * S $ Assim pela confluência $ \ existe u. s \ to_ * u \ land t \ to_ * u $ .

Por que essa abordagem não está correta?

Answer 1

$ s \ leftrightarrow ^ * t $ não significa que $ s \ righttarrow ^ * t $ e $ t \ rightarrow ^ * s $ ! Significa que existe uma cadeia de reduções $ s= s_0 \ rightleftharpoons_1 s_1 \ rightleftharpoons_2 s_2 \ rightleftharpoons_3 \ cdoz \ rightleftharpoons_n s_n= t $ onde cada uma das $ \ rightleftharpoons_i $ pode ser $ \ rightarrow $ ou $ \ landdrow $ . As instruções podem alternar qualquer número de vezes.

A propriedade Confluence implica genericamente que, se $ s \ leftrightarrow ^ * t $ então existe $ W $ < / Span> Tal que $ s \ rightarrow ^ * w \ lentower ^ * t $ , mas é preciso um pouco mais trabalho para mostrá-lo. Você pode combinar reduções na $ s \ leftrightarrow ^ * t $ para agrupar reduções consecutivas na mesma direção juntos: $ s= T_0 \ landdrow ^ * u_1 \ righttarrow ^ * t_1 \ landarrow ^ * u_2 \ righttarrow ^ * t_2 \ landarrow ^ * \ cdots \ \ * u_n \ righttarrow ^ * t_n= t $ . Por confluência em $ t_ {n-1} \ \ * u_n \ righttarrow ^ * t_n $ , existe $ v_n $ tal que $ t_ {n-1} \ righttarrow ^ * v_n \ landdarw ^ * t_n $ . Então, temos $ t_ {N-2} \} {N-1} {N-1} \ Rightarrow ^ * t_ {N-1} \ \ Rightarrow ^ * v_n \ landarrow ^ * t_n $ .

$$ \ begin {matrix} & U_1 & & & & & & u_ {N-1} & & & u_n & & \\ & _ * \ \ swarrow & & \ searrow ^ * & \ cdoots & & _ * \ swarrow & & \ Searrow ^ * & _ * \ swarrow & \ Searrow ^ * & \\ T_0 & & & & t_1 & & t_ {n-2} & & & & t_ {n-1} & & & & t_n \\ & & & & & & & & \ color {green} {\ searrow ^ *} & \ color {green} {_ * \ swarrow} & \\ & & & & & & & & \ color {green} {v_n} & \\ \ fim {matrix} $$

Agora aplique a propriedade Confluence novamente para $ t_ {n-2} \ * u_ {n-1} \ righttarrow ^ * v_n $ , ficando < span class="contentor de matemática"> $ v_ {n-1} $ tal que $ t_ {n-2} \ \ * v_ {n-1} \ \ ^ * v_n \ landarrow ^ * t_n $ . Repita até que você obtenha $ w= v_1 $ tal que $ t_0 \ righttarrow ^ * v_1 \ landdarrow ^ * t_n $ . Formalmente, esta é uma prova por indução sobre o número de alterações de direções na cadeia $ s \ leftrightarrow ^ * t $ . A confluência permite remover uma alternância de cada vez. Em mais linguagem colorida, a confluência permite que você "pop um vinco"; Cada vez que você aparece um vinco, você se junta a duas depressões juntos, e se você continuar fazendo isso, você eventualmente recebe uma única depressão.