Was ist der Unterschied zwischen LTL und CTL?

12

Ich las bereits Beispiele für Formeln in CTL , aber nicht in LTL und umgekehrt, aber ich habe Probleme , ein mentales Verständnis für LTL Formeln zu gewinnen und wirklich , was im Herzen ist der Unterschied.

lo.logic model-checking temporal-logic Anonymer Feigling
quelle
1
Viele Notizen in den Interwebs befassen sich mit diesem Thema. Haben Sie nach "dem Unterschied zwischen LTL und CTL" gegoogelt?
Dave Clarke
1
Versuchen Sie, einfache Formeln aufzuschreiben und ihre Semantik auf Kripke-Strukturen zu bewerten.
Vijay D

Antworten:

21

Um den Unterschied zwischen LTL und CTL wirklich zu verstehen, müssen Sie die Semantik beider Sprachen studieren. LTL-Formeln bezeichnen Eigenschaften, die bei jeder Ausführung eines Programms interpretiert werden. Für jede mögliche Ausführung (einen Lauf), die als Folge von Ereignissen oder Zuständen in einer Zeile angezeigt werden kann - und deshalb als "lineare Zeit" bezeichnet wird - wird die Erfüllbarkeit des Laufs überprüft, ohne dass die Möglichkeit besteht, zu einem anderen Lauf zu wechseln während der Überprüfung. Andererseits überprüft die CTL-Semantik eine Formel für alle möglichen Läufe und versucht entweder alle möglichen Läufe ( A- Operator) oder nur einen Lauf ( E- Operator), wenn sie einem Zweig gegenübersteht.

In der Praxis bedeutet dies, dass einige Formeln jeder Sprache nicht in der anderen Sprache angegeben werden können. Beispielsweise besagt die Reset-Eigenschaft (eine wichtige Erreichbarkeitseigenschaft für das Schaltungsdesign), dass immer die Möglichkeit besteht, dass ein Zustand während eines Laufs erreicht werden kann, auch wenn er nie tatsächlich erreicht wird ( AG EF-Reset ). LTL kann nur angeben, dass der Rücksetzstatus tatsächlich erreicht wurde und nicht, dass er erreicht werden kann.

◊◻s◊◻s

Ich weiß nicht, ob dies Ihre Frage beantwortet, aber ich möchte einige Kommentare hinzufügen.

Es wird viel über die beste Logik diskutiert, um Eigenschaften für die Softwareüberprüfung auszudrücken ... aber die eigentliche Debatte ist woanders. LTL kann wichtige Eigenschaften für die Modellierung von Softwaresystemen (Fairness) ausdrücken, wenn die CTL eine neue Semantik (eine neue Erfüllbarkeitsrelation) haben muss, um sie auszudrücken. CTL-Algorithmen sind jedoch normalerweise effizienter und können BDD-basierte Algorithmen verwenden. Also ... es gibt keine beste Lösung. Bisher nur zwei verschiedene Ansätze.

Einer der Kommentatoren schlägt Vardis Artikel "Branching versus Linear Time: Final Showdown" vor .

Benoît Fraikin
quelle
siehe eine Diskussion über LTL vs CTL von Vardi: "Branching vs. Linear Time: Final Showdown"
Guy
Vielen Dank, das ist genau die Art von Einsicht, nach der ich gesucht habe!
Anonymer Feigling
1

Wenn Sie ein Objekt erhalten (z. B. Trace bei LTL), betrachten Sie für jeden Zeitpunkt nur eine Zukunft. In CTL haben Sie eine Vielzahl davon.

Gibt insbesondere nexteine eindeutige Aktion in LTL, aber (möglicherweise) einen ganzen Satz in CTL.

Raphael
quelle
6
Normalerweise wenden Sie die LTL-Formel jedoch auf alle Läufe des Systems an und nicht nur auf einen, wodurch die Lücke zwischen dem einen / den vielen zukünftigen Problemen geschlossen wird. Es wäre genauer zu sagen, dass LTL sich mit linearer Zeit befasst, während CTL sich mit Verzweigungszeit befasst.
Dave Clarke
4
Zu sagen, dass Sie in LTL eine Zukunft betrachten, ist wie zu sagen, dass Sie in CTL einen Zustand betrachten. Zufriedenheit wird so definiert. Es geht nicht darum, wie viele Futures es gibt, sondern um die Struktur der Zukunft. In einem ist es eine Spur, in dem anderen ein Baum.
Vijay D
@ Vijay - in der Tat ist die Struktur wichtig. Sie können beispielsweise nicht einfach eine LTL-Formel nehmen, sie wie FGp -> AF AG p transformieren und eine äquivalente CTL-Formel erhalten (diese beiden Formeln sind nicht äquivalent; außerdem ist FGp in CTL nicht exprimierbar und AF AG p ist in LTL nicht exprimierbar ).
JKFF
Ich nahm an, dass das OP mit der formalen Definition vertraut war und nach einer Art Intuition fragte, daher mein Versuch. Kann diese Antwort gerettet werden, indem man "eine Zukunft pro Modell" sagt?
Raphael
Ich kann nicht sagen, womit das OP vertraut ist. Ist ihnen zum Beispiel klar, was ein Modell jeweils ist?
Vijay D