Warum

9

Es ist bekannt, dass die zeitliche Logik LTL, CTL, CTL * in den Kalkül übersetzt / eingebettet werden kann. Mit anderen Worten, der (modale) Kalkül fasst diese Logik zusammen (dh er ist ausdrucksvoller).μμ

Könnten Sie mir bitte erklären / auf Papiere / Bücher verweisen, die diese Angelegenheit näher erläutern? Gibt es insbesondere konkrete Eigenschaften für Fairness, Lebendigkeit usw., die nicht in der zeitlichen Logik, sondern im Kalkül zum Ausdruck kommen?μ

Dimiter
quelle

Antworten:

8

Informationen zu einer Kalkülformel, die in CTL * nicht ausgedrückt werden kann, finden Sie in diesem Beitrag .μ

Bei Texten zu diesem Thema werden Sie wahrscheinlich durch das Lesen von Artikeln weiter vorankommen, da diese Themen in vielen Büchern nicht behandelt werden. Dennoch kann das Handbuch der modalen Logik ein guter Anfang sein.

Versuchen Sie für Papiere:

Ausdruckskraft der zeitlichen Logik

Diese Doktorarbeit

Emersons Modellprüfung und der Mu-Kalkül

Und es gibt noch viel mehr. Nur Google-Begriffe wie "Ausdruckskraft", "Mu-Kalkül" und "zeitliche Logik".

Shaull
quelle
Danke für das Beispiel und die Vorschläge. Könnten Sie bitte relevante Papiere vorschlagen? Ich erinnere mich, einige in der Vergangenheit gesehen zu haben, aber es fällt mir schwer, sie jetzt zu finden ...
Dimiter
Papiere zur Antwort hinzugefügt.
Shaull
Es gibt jetzt ein Buch über das Modellieren mit mCRL2 (eine ungefähre Vorstellung von dessen Inhalt finden Sie in der Buchankündigung ).
Reinierpost
4

Der Kalkül ist streng ausdrucksstärker als LTL, CTL und CTL *. Dies ist eine Folge einiger unterschiedlicher Ergebnisse.μ

Der erste Schritt besteht darin zu zeigen, dass der Kalkül so ausdrucksstark ist wie die zeitliche Logik. Die Hauptidee für die Codierung dieser Logiken besteht darin, zeitliche Eigenschaften als Fixpunkte zu erkennen. Auf einer sehr informellen Ebene können Sie mit den kleinsten Fixpunkten Eigenschaften endlicher Natur ausdrücken, und die größten Fixpunkte gelten für unendliche Eigenschaften. Zum Beispiel definiert schließlich φ in LTL, dass es in der endlichen Zukunft einen Moment gibt, zu dem φ wahr ist, während φ immer angibt, dass φμφφφφist wahr in einer unendlichen Anzahl von zukünftigen Zeitschritten. In Bezug auf Fixpunkte würde die Eigenschaft eventuell unter Verwendung eines kleinsten Fixpunkts und die Eigenschaft always unter Verwendung eines größten Fixpunkts ausgedrückt. Nach einer solchen Intuition können zeitliche Operatoren als Festpunktoperatoren codiert werden.

Der nächste Schritt besteht darin zu zeigen, dass der Kalkül ausdrucksvoller ist. Die Hauptidee ist die Wechseltiefe. Fixpunkte wechseln sich ab, wenn ein kleinster Fixpunkt den größten Fixpunkt beeinflusst und umgekehrt. Die Wechseltiefe einer μ- Kalkülformel zählt die Anzahl der darin auftretenden Wechsel. Die Operatoren in CTL können durch μ- Kalkülformeln mit Wechseltiefe 1 codiert werden . Die Operatoren in CTL * und LTL können durch μ- Kalkülformeln mit einer Wechseltiefe von höchstens 2 codiert werden . Die Wechselhierarchie der μμμμ1μ2μ-calculus ist streng, was bedeutet, dass Sie mit zunehmender Wechseltiefe in einer Formel streng mehr Eigenschaften ausdrücken können. Aus diesem Grund sagen die Leute, dass der Kalkül ausdrucksvoller ist als diese zeitliche Logik.μ

Einige Referenzen:

  1. Die anfänglichen Argumente, dass der Kalkül mehrere Logiken zusammenfasst, erscheinen in Modalitäten für die Modellprüfung: Verzweigungszeitlogik schlägt zurück , Emerson und Lei, 1985.μ
  2. μmu
  3. μ
  4. μ
  5. μ

μμ

Vijay D.
quelle
Vielen Dank für eine tolle Antwort! Zu Ihrem Kommentar zum Dienstprogramm: Angenommen, ich möchte einen μ-Kalkül-Modellprüfer verwenden, aber die Dinge in der zeitlichen Logik angeben, was einfacher ist. Gibt es eine Technik (noch besser ein Werkzeug), die Formeln in einer dieser Logiken (CTL, CTL * oder LTL) automatisch in den μ-Kalkül übersetzt? Vielen Dank!
Dimiter
μ
2

Es ist gut bekannt, dass μEINμX..EINX.

phs
quelle