Was ist Coinduktion?

Ich habe von (struktureller) Induktion gehört. Es erlaubt Ihnen, endliche Strukturen aus kleineren Strukturen aufzubauen, und es gibt Ihnen Beweise für die Überlegung solcher Strukturen. Die Idee ist klar genug.

Aber was ist mit der Coinduktion? Wie funktioniert es? Wie kann man etwas aussagekräftiges über eine unendliche Struktur sagen?

Es gibt (mindestens) zwei Aspekte, die angesprochen werden müssen, nämlich die Koinduktion als Methode zur Definition von Dingen und als Beweisverfahren.

Welche Beziehung besteht zwischen Coinduktion und Bisimulation, wenn man die Coinduktion als Beweismethode betrachtet?

Erstens, um eine mögliche kognitive Dissonanz zu beseitigen: Das Denken über unendliche Strukturen ist kein Problem, wir tun es die ganze Zeit. Solange die Struktur endlich beschreibbar ist, ist das kein Problem. Hier sind einige gebräuchliche Arten von unendlichen Strukturen:

• Sprachen (Sätze von Zeichenketten über einem Alphabet, die endlich sein können);
• Baumsprachen (Baumgruppen über einem Alphabet);
• Ausführungsspuren eines nicht deterministischen Systems;
• reale Nummern;
• Mengen von ganzen Zahlen;
• Mengen von Funktionen von ganzen Zahlen zu ganzen Zahlen; …

Koinduktivität als größter Fixpunkt

Wo induktive Definitionen eine Struktur aus elementaren Bausteinen bilden, formen koin- duktive Definitionen Strukturen, aus denen sie dekonstruiert werden können. Der Listentyp, dessen Elemente sich in einer Menge befinden, Aist beispielsweise in Coq wie folgt definiert:

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

Informell ist der listTyp der kleinste Typ, der alle aus den Konstruktoren nilund gebildeten Werte enthält cons, mit dem Axiom . Umgekehrt können wir den größten Typ definieren, der alle Werte enthält, die aus diesen Konstruktoren erstellt wurden, wobei das Unterscheidungsaxiom beibehalten wird:$\forall x \, y, \: \mathtt{nil} \ne \mathtt{cons} \: x \: y$

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

listist isomorph zu einer Teilmenge von colist. Darüber hinaus colistenthält unendliche Listen: Listen mit coconsauf cocons.

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

flipflopist die unendliche (zirkuläre Liste) ; ist die unendliche Liste natürlicher Zahlen .$1::2::1::2::\ldots$from 0$0::1::2::\ldots$

Eine rekursive Definition ist wohlgeformt, wenn das Ergebnis aus kleineren Blöcken besteht: Rekursive Aufrufe müssen bei kleineren Eingaben funktionieren. Eine kernkursive Definition ist wohlgeformt, wenn das Ergebnis größere Objekte erzeugt. Induktion befasst sich mit Konstruktoren, Koinduktion befasst sich mit Destruktoren. Beachten Sie, wie sich die Dualität nicht nur von kleiner zu größer ändert, sondern auch von Eingängen zu Ausgängen. Beispielsweise ist der Grund, warum die obigen Definitionen flipflopund fromwohlgeformt sind, dass der kerncursive Aufruf coconsin beiden Fällen durch einen Aufruf an den Konstruktor geschützt wird.

Wo Aussagen über induktive Objekte induktive Beweise haben, haben Aussagen über koinduktive Objekte koinduktive Beweise. Definieren wir beispielsweise das unendliche Prädikat für Colists. intuitiv sind es die unendlichen Kolisten, die nicht enden conil.

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

Um zu beweisen, dass Kolisten der Form from nunendlich sind, können wir durch Coinduktion argumentieren. from nist gleich cocons n (from (1 + n)). Dies zeigt, dass from ngrößer als from (1 + n), was nach der Coinduktionshypothese from nunendlich ist , also unendlich ist.

Bisimilarität, eine coinduktive Eigenschaft

Die Coinduktion als Beweismethode gilt auch für Gegenstände im Haushalt. Intuitiv ausgedrückt basieren induktive Beweise über ein Objekt darauf, wie das Objekt aufgebaut ist. Coinductive Proofs basieren darauf, wie das Objekt zerlegt werden kann.

Beim Studium deterministischer Systeme ist es üblich, Äquivalenz durch induktive Regeln zu definieren: Zwei Systeme sind äquivalent, wenn Sie durch eine Reihe von Transformationen von einem zum anderen gelangen können. Solche Definitionen erfassen in der Regel nicht, auf welche Weise nicht deterministische Systeme trotz unterschiedlicher interner Struktur dasselbe (beobachtbare) Verhalten aufweisen können. (Coinduction ist auch nützlich, um nicht terminierende Systeme zu beschreiben, auch wenn sie deterministisch sind, aber darauf werde ich mich hier nicht konzentrieren.)

Nichtdeterministische Systeme wie gleichzeitige Systeme werden häufig durch markierte Übergangssysteme modelliert . Ein LTS ist ein gerichteter Graph, in dem die Kanten beschriftet sind. Jede Kante repräsentiert einen möglichen Übergang des Systems. Eine Spur eines LTS ist die Folge von Kantenbeschriftungen über einem Pfad im Diagramm.

Zwei LTS können sich identisch verhalten, indem sie die gleichen möglichen Spuren haben, auch wenn ihre interne Struktur unterschiedlich ist. Der Graphisomorphismus ist zu stark, um seine Äquivalenz zu definieren. Stattdessen wird eine LTS soll simulieren andere LTS , wenn jeder Übergang des zweiten LTS einen entsprechenden Übergang in dem ersten zugibt. Formal sei die disjunkte Vereinigung der Zustände der beiden LTS, die (gemeinsame) Menge von Bezeichnungen und die Übergangsrelation. Die Beziehung ist eine Simulation, wenn $\mathscr{A}$$\mathscr{B}$$S$$L$$\rightarrow$$R \subseteq S \times S$

$\mathscr{A}$ simuliert wenn es eine Simulation gibt, bei der alle Zustände von mit einem Zustand in . Wenn eine Simulation in beide Richtungen ist, spricht man von einer Bisimulation . Simulation ist eine koinduktive Eigenschaft: Jede Beobachtung auf einer Seite muss auf der anderen Seite übereinstimmen.$\mathscr{B}$$\mathscr{B}$$\mathscr{A}$$R$

Es gibt möglicherweise viele Bisimulationen in einem LTS. Unterschiedliche Bisimulationen können unterschiedliche Zustände identifizieren. Bei zwei Bisimulationen und ist die durch Vereinigung der Beziehungsgraphen gegebene Beziehung selbst eine Bisimulation, da verwandte Zustände verwandte Zustände für beide Beziehungen hervorrufen. (Dies gilt auch für unendliche Vereinigungen. Die leere Beziehung ist eine uninteressante Bisimulation, ebenso wie die Identitätsbeziehung.) Insbesondere ist die Vereinigung aller Bisimulationen selbst eine Bisimulation, die als Bisimilarität bezeichnet wird. Bisimilarität ist die gröbste Art, ein System zu beobachten, das nicht zwischen verschiedenen Zuständen unterscheidet.$R_1$$R_2$$R_1 \cup R_2$

Bisimilarität ist eine coinduktive Eigenschaft. Es kann als der größte Fixpunkt eines Operators definiert werden: Es ist die größte Beziehung, die, wenn sie erweitert wird, um äquivalente Zustände zu identifizieren, dieselbe bleibt.

Verweise

• Coq und der Kalkül von induktiven Konstruktionen

  • Yves Bertot und Pierre Castéran. Interaktive Theoremprüfung und Programmentwicklung - Coq'Art: Die Berechnung induktiver Konstruktionen . Springer, 2004. Ch. 13. [ Website ] [ Amazon ]
  • Eduardo Giménez. Eine Anwendung von co-induktiven Typen in coq: Überprüfung des Alternating-Bit-Protokolls . In Workshop über Typen für Beweise und Programme , Nummer 1158 in Lecture Notes in Computer Science , S. 135–152. Springer-Verlag, 1995. [ Google Books ]
  • Eduardo Giménez und Pierre Castéran. Ein Tutorial zu [Co-] Induktiven Typen in Coq. 2007. [ PDF ]

• Markierte Übergangssysteme und Bisimulationen

  • Robin Milner. Kommunikation und Nebenläufigkeit . Prentice Hall, 1989.
  • Davide Sangiorgi. Über die Ursprünge von Bisimulation und Coinduktion . ACM-Transaktionen zu Programmiersprachen und -systemen (TOPLAS), Band 31, Ausgabe 4, Mai 2009. [ PDF ] [ ACM ] Zugehörige Kursfolien: [ PDF ] [ CiteSeer ]

  • Davide Sangiorgi. Der Pi-Kalkül: Eine Theorie mobiler Prozesse . Cambridge University Press, 2003. [ Amazon ]

    • Weitere Referenzen von Anton Trunov vorgeschlagen

  • Ein Kapitel in Certified Programming with Dependent Types von A. Chlipala

  • D. Sangiorgi. "Einführung in Bisimulation und Coinduction". 2011. [ PDF ]
  • D. Sangiorgi und J. Rutten. Fortgeschrittene Themen in Bisimulation und Coinduktion . Cambridge University Press, 2012. [ CUP ]

Betrachten wir die folgende induktive Definition:

$\qquad \displaystyle \begin{align*} &\phantom{\Rightarrow} \quad \varepsilon \in \mathcal{T} \\ w \in \mathcal{T} \quad &\Rightarrow \quad aw \in \mathcal{T}\\ aw \in \mathcal{T} \quad &\Rightarrow \quad baw \in \mathcal{T} \end{align*}$

Was ist ? Es ist klar, die Menge der Zeichenfolgen ohne zwei aufeinanderfolgende , dh$\mathcal{T}$$b$

$\qquad \displaystyle \mathcal{T} =\{\varepsilon, a, aa, ba, aaa, aba, \dots\} = \mathcal{L}\left((ba\mid a)^*\right) \subseteq \Sigma^*.$

Richtig? Wir brauchen dafür den harmlosen Satz "und ist die kleinste Menge, die diese Bedingungen erfüllt". Richtig, da sonst auch funktionieren würde.$\mathcal{T}$$\mathcal{T}=\{a,b\}^*$

Aber es steckt noch mehr dahinter. Schreiben Sie die obige Definition als (monotone) Funktion :$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\}$

Jetzt ist der kleinste Fixpunkt von . Da monoton ist und ein vollständiges Gitter ist , sagt uns das Knaster-Tarski-Theorem , dass solch ein kleinster Fixpunkt existiert und eine richtige Sprache ist. Da dies mit jeder vernünftigen induktiven Definition funktioniert, sprechen wir normalerweise nicht darüber. Es passt einfach zu unserer Intuition: Wir beginnen mit und wenden die Regeln Schritt für Schritt an. im Limit erhalten wir .$\mathcal{T}$$f$$f$$\left(2^{\Sigma^\infty},\subseteq\right)$$\{\varepsilon\}$$\mathcal{T}$

Jetzt drehen wir die Dinge um. Anstatt zu sagen "wenn enthalten ist, ist es auch ", sagen wir "wenn enthalten ist, muss es auch ". Wir können den Anker nicht drehen, also geht er weg. Das läßt uns mit einem Problem: wir haben zu ergreifen , um die Lage sein , lange willkürlich entfernt Präfixe von jedem Wort in und bleiben in ! Dies ist mit endlichen Worten nicht möglich; gut, dass ich mich oben in ! Wir erhalten die Menge der unendlichen Wörter ohne Faktor (Teilzeichenfolge) , dh .a w a w w T ' T ' Σ ∞ b b T ' = L ( ( b a ∣ a ) ω $w$$aw$$aw$$w$$\mathcal{T}'$$\mathcal{T}'$$\Sigma^\infty$$bb$$\mathcal{T}'=\mathcal{L}\left((ba\mid a)^\omega\right)$

In Bezug auf ist der größte Fixpunkt². Das ist eigentlich sehr intuitiv: Wir können nicht hoffen, von unten zu treffen , dh induktiv, indem wir von und Dinge hinzufügen , die die Regeln erfüllen, also gehen wir von oben aus , dh koinduktiv, indem wir beginnen aus entfernen und Dinge, die nicht den Regeln entsprechen.T ' T ' { ε } Σ $f$$\mathcal{T}'$$\mathcal{T}'$$\{\varepsilon\}$$\Sigma^\infty$

Notation:

• $\Sigma^\infty = \Sigma^* \cup \Sigma^\omega$
• $\Sigma^\omega$ ist die Menge aller unendlichen Folgen über .$\Sigma$

¹ Du darfst keine Dinge wie tun ; die entsprechende Funktion wäre nicht monoton. ² Wir müssen irgendwie unter den Teppich kehren . { ε $w \in \mathcal{T} \Rightarrow aw \notin \mathcal{T}$
$\{\varepsilon\}$