共誘導とは何ですか？

cs.stackexchange https://cs.stackexchange.com/questions/525

質問

（構造的な）誘導について聞いたことがあります。これにより、小さな構造から有限構造を構築することができ、そのような構造について推論するための証拠原則を提供します。アイデアは十分に明確です。

しかし、共謀はどうですか？どのように機能しますか？無限の構造について決定的なことをどのように言うことができますか？

（少なくとも）対処すべき2つの角度、すなわち、物事を定義する方法として、そして証明技術としての共誘導があります。

共誘導に関して、証明技術として、共誘導と二項化の関係は何ですか？

役に立ちましたか？

解決

第一に、認知的不協和音を払拭するために：無限の構造についての推論は問題ではありません。私たちは常にそれを行います。構造が有限である限り、それは問題ではありません。ここに、いくつかの一般的なタイプの無限構造があります：

  • 言語（いくつかのアルファベットの上の文字列のセット。これは有限かもしれません）;
  • 木言語（いくつかのアルファベット上の木のセット）;
  • 非決定的システムの実行トレース。
  • 実数;
  • 整数のセット;
  • 整数から整数への関数のセット。 …

最大の固定点としての共誘導性

帰納的定義が基本的な構成要素から構造を構築する場合、共同定義は、それらの分解方法から構造を形成します。たとえば、要素がセットにあるリストのタイプ A COQで次のように定義されています。

Inductive list (A:Set) : Set :=
  | nil : list A
  | cons : A -> list A -> list A.

非公式に、 list タイプは、から構築されたすべての値を含む最小タイプです nil と cons コンストラクター。逆に、これらのコンストラクターから構築されたすべての値を含む最大のタイプを定義し、識別公理を維持できます。

CoInductive colist (A:Set) : Set :=
  | conil : colist A
  | cocons : A -> colist A -> colist A.

list のサブセットと同型です colist. 。加えて、 colist 無限のリストが含まれています。リスト cocons その上 cocons.

CoFixpoint flipflop : colist ℕ := cocons 1 (cocons 2 flipflop).
CoFixpoint from (n:ℕ) : colist ℕ := cocons n (from (1 + n)).

flipflop IS Infinite（Circular List）$ 1 :: 2 :: 1 :: 2 :: ldots $; from 0 自然数の無限のリスト$ 0 :: 1 :: 2 :: ldots $。

結果が小さなブロックから構築されている場合、再帰的な定義はよく形成されます。再帰呼び出しは、より小さな入力で動作する必要があります。結果がより大きなオブジェクトを構築する場合、coreCursiveの定義はよく形成されます。誘導はコンストラクターを見て、共誘導はデストラクタを見ます。二重性が小さくて大きくなるだけでなく、出力への入力もどのように変化するかに注意してください。たとえば、理由 flipflop と from 上記の定義はよく形成されていることは、corecursiveの呼び出しが、 cocons 両方の場合のコンストラクター。

帰納的オブジェクトに関する声明には帰納的証拠がある場合、共同誘導物体に関する声明には共誘導性証明があります。たとえば、コリストの無限の述語を定義しましょう。直感的には、無限のコリストは終わらないものです conil.

CoInductive Infinite A : colist A -> Prop :=
  | Inf : forall x l, Infinite l -> Infinite (cocons x l).

その形式のコリストを証明するために from n 無限であり、共誘導によって推論することができます。 from n に等しい cocons n (from (1 + n)). 。これはそれを示しています from n より大きい from (1 + n), 、これは共誘導仮説によって無限です。 from n 無限です。

二極化、共誘導特性

証明手法としての共誘導は、フィンタリーオブジェクトにも適用されます。直感的に言えば、オブジェクトに関する帰納的証明は、オブジェクトの構築方法に基づいています。共誘導性証明は、オブジェクトの分解方法に基づいています。

決定論的システムを研究する場合、誘導ルールを使用して同等性を定義することが一般的です。一連の変換によって一方から他方に到達できる場合、2つのシステムが同等です。このような定義は、異なる内部構造を持っているにもかかわらず、非決定的システムが同じ（観察可能な）動作をすることになる可能性がある多くの異なる方法をキャプチャできない傾向があります。 （共誘導は、非終了システムが決定論的であっても説明するのにも役立ちますが、これは私がここで焦点を当てるものではありません。）

同時システムなどの非決定的システムは、しばしばによってモデル化されます ラベル付き遷移システム. 。 LTSは、エッジのラベルが付いた指示グラフです。各エッジは、システムの遷移の可能性を表します。 LTSのトレースは、グラフのパス上のエッジラベルのシーケンスです。

2つのLTは、内部構造が異なる場合でも、同じ可能な痕跡を持っているという点で、同じように動作する可能性があります。グラフの同等性は強すぎてそれらの等価性を定義できません。代わりに、lts $ mathscr {a} $は シミュレートします 別のLTS $ mathscr {b} $ 2番目のLTSのすべての遷移が、最初の遷移を認めている場合。正式には、$ s $を2つのLTSの状態のばらばらの連合、$ l $のラベルのセット、$ rightArrow $の移行関係とします。関係$ r subseteq s times s $は、$$ forall（p、q） in r、％ forall p ' in s、 forall alpha in l、 text {if}のシミュレーションです。 p stackrel alpha rightArrow p ' text {then} exists q'、; q stackrel alpha rightArrow q ' text {and}（p'、q '） in r $$

$ mathscr {a} $は、$ mathscr {b} $のすべての状態が$ mathscr {a} $の状態に関連しているシミュレーションがある場合、$ mathscr {b} $をシミュレートします。 $ r $が両方向のシミュレーションである場合、それは 二項. 。シミュレーションは共誘導性の特性です。一方の観察は、反対側に一致する必要があります。

LTSには潜在的に多くの二項があります。さまざまな二項化が異なる状態を特定する可能性があります。 2つの二項$ r_1 $と$ r_2 $を考えると、関連状態が両方の関係に関連する状態を生み出すため、関係グラフの結合を$ r_1 cup r_2 $を取得することによって与えられる関係は、それ自体が二項である。 （これは無限の組合にも当てはまります。空の関係は、アイデンティティの関係と同様に焦点を絞ることのない二項拡張です。）特に、すべての二重模倣の結合はそれ自体が二極化と呼ばれる二項様式です。二極性は、異なる状態を区別しないシステムを観察する最も粗い方法です。

二重類似性は共誘導的な特性です。オペレーターの最大の固定点として定義できます。これは、同等の状態を識別するために拡張された場合、同じままである最大の関係です。

参照

  • COQと誘導構造の計算

    • Yves BertotとPierreCastéran。 インタラクティブな定理証明とプログラム開発 - coq'Art：帰納的構造の計算. 。スプリンガー、2004年。Ch。 13. [Webサイト] [アマゾン]
    • エドゥアルド・ギメネス。 COQにおける共誘導タイプの適用：交互ビットプロトコルの検証. 。の 証明とプログラムの種類に関するワークショップ, 、番号1158 in コンピューターサイエンスの講義ノート, 、135〜152ページ。 Springer-Verlag、1995年。[Google Books]
    • エドゥアルド・ギメネスとピエール・カステラン。 COQの[CO-]誘導タイプに関するチュートリアル。 2007. [PDF]

  • ラベル付き遷移システムと二項型

    • ロビン・ミルナー。 コミュニケーションと並行性. 。プレンティスホール、1989年。
    • Davide Sangiorgi。 二項化と共誘導の起源について. 。プログラミング言語とシステムに関するACMトランザクション（Toplas）、第31巻問題4、2009年。[PDF] [ACM]関連するコーススライド：[PDF] [引用者]

    • Davide Sangiorgi。 Pi-calculus：モバイルプロセスの理論. 。ケンブリッジ大学出版局、2003年。[アマゾン]

    • a 章 の 従属タイプの認定プログラミング A. Chlipala

    • D. sangiorgi。 「二項化と共誘導の紹介」。 2011. [PDF]
    • D. SangiorgiとJ. Rutten。 二項化と共誘導における高度なトピック. 。ケンブリッジ大学出版局、2012年。カップ]

他のヒント

次の誘導定義を考えてみましょう。

$ qquad displaystyle begin {align*}＆ phantom { rightArrow} quad varepsilon in mathcal {t} in mathcal {t} quad＆ rightarrow in in in quad aw Mathcal {t} aw in mathcal {t} quad＆ rightarrow quad baw in mathcal {t} end {align*} $

$ mathcal {t} $とは何ですか？明らかに、2つの後続の$ b $がない文字列のセット、すなわち

$ qquad displaystyle mathcal {t} = { varepsilon、a、aa、ba、aaa、aba、 dots } = mathcal {l} left（（ba mid a）^* right） subseteq sigma^*。$

右？まあ、そのために必要なのは、無害な文「そして$ mathcal {t} $は、これらの条件を満たす最小のセットです」です。それ以外の場合は、$ mathcal {t} = {a、b }^*$も機能します。

しかし、それ以上のものがあります。上記の定義を（bonotone）function $ f：2^{ sigma^ infty} to 2^{ sigma^ infty} $：

$ qquad f（t）= t cup { varepsilon } cup {aw mid w in t } cup {baw mid aw in t } $

今$ mathcal {t} $は 最小のフィックスポイント $ f $の。実際、$ f $はモノトーンであり、$ left（2^{ sigma^ infty}、 subseteq right）$が 完全な格子, Knaster-Tarski定理 このような最小のフィックスポイントが存在し、適切な言語であることを教えてくれます。これは合理的な¹の帰納的定義で機能するため、通常はこれについては話しません。それは私たちの直感に適合するだけです。$ { varepsilon } $から始めて、段階的にルールを適用します。制限では、$ mathcal {t} $を取得します。

今、私たちは物事を好転させます。 「$ w $が含まれている場合、$ aw $」と言う代わりに、$ aw $が含まれている場合、$ w $である必要があります」。アンカーを回すことはできないので、消えます。それは私たちに問題を残します：私たちは取ることができなければなりません 任意に長い $ mathcal {t} '$の任意の単語から離れたプレフィックスは、$ mathcal {t}' $に残ります！これは有限の単語では不可能です。私が$ sigma^ infty $上に忍び込んだ良いこと！係数（サブストリング）$ bb $、すなわち$ mathcal {t} '= mathcal {l} left（（ba mid a）^ omega right）$ $）のない無限の単語のセットになります。

$ f $、$ mathcal {t} '$はその 最大 fixpoint²。これは実際には非常に直感的です。 下, 、すなわち、$ { varepsilon } $から起動することで誘導的に 追加 ルールを満たすものなので、私たちは その上, 、すなわち、$ sigma^ infty $から開始することにより、共誘発的に 削除 そうすること いいえ ルールに準拠しています。

表記：

  • $ sigma^ infty = sigma^* cup sigma^ omega $
  • $ sigma^ omega $はすべてのセットです 無限 $ sigma $を超えるシーケンス。

¹あなたは$ w in mathcal {t} rightArrow aw notin mathcal {t} $のようなことをすることは許可されていません。対応する関数は単調ではありません。
²何らかの形でラグの下で$ { varepsilon } $をスイープする必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top