シンプルな書き換えシステムの Confluence の証明

Question

次の用語で構成される単純な言語があると仮定します。

• $\mathtt{true}$
• $\mathtt{false}$
• $t_1,t_2,t_3$ が項の場合、$\mathtt{if}\ も同様です:t_1 \:\数学{その後}\:t_2 \:\mathtt{else}\:t_3$

ここで、次の論理評価ルールを仮定します。

$$ begin {gracked*} dfrac {} { mathtt {if} ：\mathtt{本当} \:\mathtt{そのとき}\:t_2 \:\mathtt{else}\:t_3 to t_2} text {[e-iftrue]} quad dfrac {} { mathtt {if} ：\mathtt{false} \:\mathtt{その後}\:t_2 \:\mathtt{else}\:t_3 to t_3} text {[e-iffalse]} dfrac {t_1 to t_1 '} { mathtt {if} ：t_1 \:\数学{その後}\:t_2 \:\mathtt{else}\:t_3 o \mathtt{if}\:t_1' \:\mathtt{その後}\:t_2 \:\mathtt{else}\:t_3} text {[e-if]} end {gracking*} $$

次のようなファンキーなルールも追加するとします。

$$ dfrac {t_2 to t_2 '} { mathtt {if} ：t_1 \:\数学{その後}\:t_2 \:\mathtt{else}\:t_3 o \mathtt{if}\:t_1 \:\数学{その後}\:t_2' \:\mathtt{else}\:t_3} text {[e-fiffunny]} $$

与えられた評価ルールを持つこの単純な言語について、次のことを証明したいと思います。

定理：$r ightarrow s$ と $r ightarrow t$ の場合、$s ightarrow u$ や $t ightarrow u$ などの項 $u$ が存在します。

これを $r$ の構造に関する帰納法によって証明しています。これがこれまでの私の証明です。すべてうまくいきましたが、最後のケースで行き詰まっています。$r$ の構造に関する帰納法では十分ではないようですが、誰か助けてくれませんか?

証拠。 $r$ の帰納法により、$r$ が取り得るすべての形式を分離します。

1. $r$ は定数ですが、正規形は何も評価されないため、証明する必要はありません。
2. $r=$ true の場合は $r_2$、そうでない場合は $r_3$。(a) 両方の導出は E-IfTrue ルールを使用して行われました。この場合 $s=t$ なので証明できるものは何もありません。(b) 1 つの導出は E-IfTrue ルールを使用して行われ、もう 1 つは E-Funny ルールを使用して行われました。$r ightarrow s$ が E-IfTrue で行われたと仮定すると、他のケースも同様に証明されます。$s = r_2$ であることがわかりました。また、$t =$ if true then $r'_2$ else $r_3$ であること、および何らかの導出 $r_2 ightarrow r'_2$ (前提) が存在することもわかっています。ここで $u = r'_2$ を選択すると、このケースは終了します。
3. $r=$ false の場合は $r_2$、それ以外の場合は $r_3$。上記と同様に証明されています。
4. $r=$ if $r_1$ then $r_2$ else $r_3$ with $r_1 eq $ true または false。(a) 両方の導出は E-If ルールを使用して行われました。$s =$ if $r'_1$ then $r_2$ else $r_3$ と $t =$ if $r''_1$ then $r_2$ else $r_3$ であることがわかりました。また、派生 $r_1 ightarrow r'_1$ と $r_1 ightarrow r''_1$ (前提) が存在することもわかっています。これで、帰納仮説を使用して、 $r'_1 ightarrow r'''_1$ および $r''_1 ightarrow r'''_1$ のような項 $r'''_1$ が存在すると言うことができます。$u =$ if $r'''_1$ then $r_2$ else $r_3$ として、E-If ルールにより $s ightarrow u$ と $t ightarrow u$ が成り立つことに注目して、このケースを結論付けます。(b) 1 つの導出は E-If ルールによって行われ、もう 1 つは E-Funny ルールによって行われました。

この後者のケース、つまり 1 つの導出が E-If によって行われ、もう 1 つが E-Funny によって行われたのが、私が見逃しているケースです...仮説が使えないようです。

ご協力をよろしくお願いいたします。

Answer 1

さて、$r = \mathtt{if}\ の場合を考えてみましょう。t_1 \:\数学{その後}\:t_2 \:\mathtt{else}\:t_3$、$s$ は E-If ルールを適用することによって導出され、$t$ は E-Funny ルールを適用することによって導出されます。したがって $s = \mathtt{if}\:t'_1 \:\数学{その後}\:t_2 \:\mathtt{else}\:t_3$ ここで、$t_1 ightarrow t'_1$ および $t = \mathtt{if}\:t_1 \:\数学{その後}\:t'_2 \:\mathtt{else}\:t_3$ ここで、$t_2 ightarrow t'_2$。

探している $u$ は $u = \mathtt{if}\ です。t'_1 \:\数学{その後}\:t'_2 \:\mathtt{else}\:t_3$。$s ightarrow u$ はルール E-Funny からに従い、$t ightarrow u$ はルール E-If からに従います。

Answer 2

これを調べる場合は、少し専門用語が役に立つかもしれません。これらのルールは 書き換える ルール, 、型システムとは何の関係もありません¹。証明しようとしているプロパティは次のように呼ばれます 合流;より具体的に言うと、それは 強い合流:あるステップで項をさまざまな方法で簡約できる場合、次のステップで項を収束させることができます。一般に、Confluence では 1 つだけではなく、任意の数のステップを実行できます。$r o^*s$ と $r o^*t$ の場合、$s o^*u$ と $t o^*u$ のような $u$ が存在します — 項を短縮できる場合さまざまな方法で、どれだけ乖離していても、最終的には再び収束します。

このような帰納的に定義された書き換えルールの特性を証明する最良の方法は、縮小された項の構造ではなく、縮小の導出構造に対する帰納法です。ここでは、ルールが左側の項の構造に従っているため、どちらでも機能しますが、ルールに基づく推論はより簡単です。用語に飛び込む代わりに、ルールのすべてのペアを取得し、両方の左辺となる用語を確認します。この例では、最終的には同じケースが得られますが、少し速くなります。

問題が発生した場合、一方は「if」の部分を減らし、もう一方は「then」の部分を減らします。変化する 2 つの部分 ([E-If] の $t1$、[E-IfFunny] の $t_2$) の間に重複はなく、[E-If] の $t_2$ または $t_1$ には制約がありません。 [E-IfFunny]で。したがって、両方のルールが適用される項がある場合、$\mathtt{if}\ の形式でなければなりません。r_1 \:\数学{その後}\:r_2 \:\mathtt{else}\:r_3$ の場合、ルールを次のいずれかの順序で適用することを選択できます。

$$ begin {array} {rcl}＆ mathtt {if} ：r_1 \:\数学{その後}\:r_2 \:\mathtt{else}\:r_3＆ { small text {[e-if]}}} swarrow＆ searrow { small text {[e-fiffunny]}} mathtt {if} ：r_1' \:\数学{その後}\:r_2 \:\mathtt{else}\:r_3 & & \mathtt{if}\:r_1 \:\数学{その後}\:r_2' \:\mathtt{else}\:r_3 { small text {[e-iffunny]}} searrow＆＆ swarrow { small text {[e-fif]}} ＆ mathtt {if} ：r_1' \:\数学{その後}\:r_2' \:\mathtt{else}\:r_3＆ end {array} $$

¹ _{型と書き換えが一緒に行われることがありますが、本質的にはそれらは直交する概念です。}