Wie kann ich manuell entscheiden, ob zwei CTL-Formeln gleichwertig sind?

8

Angenommen, ich habe zwei Formeln und (über denselben Satz von Atomsätzen ) in CTL . Wir haben das iff für alle Übergangssysteme über . $\Phi$ $\Psi$ $AP$ $\Phi \equiv \Psi$ $Sat_{TS}(\Phi) = Sat_{TS}(\Psi)$ $TS$ $AP$

Da es unendlich viele Übergangssysteme gibt, ist es unmöglich, alle zu überprüfen. Ich habe darüber nachgedacht, PNF (Positive Normal Form, Negation nur neben Literalen) zu verwenden, da es nach seinem Namen die gleiche Formel für wie für wenn sie gleichwertig sind, aber ich bin nicht überzeugt, dass dies funktioniert Alle Fälle (man könnte sagen, ich bin nicht davon überzeugt, dass PNF tatsächlich eine normale Form ist). $\Phi$ $\Psi$

Nehmen Sie zum Beispiel $\forall \mathrm{O} \forall \lozenge \Phi_0 \stackrel{?}{\equiv} \forall \lozenge \forall \mathrm{O} \Phi_0$ (wobei $\mathrm{O}$ der nextOperator ist und $\lozenge$ ist der eventuallyOperator). Ich suche nach einer Möglichkeit, dies von Hand zu tun.

logic model-checking computation-tree-logic Bitmaske
quelle

Was ist ? Die Formel erfüllt das Übergangssystem? Ich gehe davon aus, dass Ihre Definition eines Übergangssystems dann einen Anfangszustand enthält und die Formel in diesem Zustand überprüft wird.

S a t_{T S}

$Sat_{TS}$

Vijay D

@VijayD: ist die Menge der Zustände von TS, für die ab einem dieser Zustände die Formel erfüllt ist.

S a t_{T S}

$Sat_{TS}$

Bitmaske

6

Es scheint mir, dass " " gleichbedeutend ist mit "Weder noch ist erfüllbar". $\Phi≡\Psi$ $(\Phi ∧ ¬\Psi)$ $(\Psi ∧ ¬\Phi)$

Daher ist die Entscheidung über die Äquivalenz ebenso schwierig wie die Entscheidung über die Erfüllbarkeit, da " erfüllbar" gleichbedeutend mit "nicht ( )" ist. $\Phi$ $¬\Phi≡\top$

In diesem Artikel wird ein exponentielles Verfahren erwähnt, um die Erfüllbarkeit in CTL zu bestimmen. Daher sollte es ausreichen, den Algorithmus mit den beiden oben beschriebenen Formeln auszuführen.

PS: Ich bin überhaupt kein Experte auf diesem Gebiet, also überprüfen Sie bitte, was ich geschrieben habe. Wenn dies sinnvoll ist, werde ich die verschiedenen "scheint" und "sollte" entfernen.

jmad
quelle

Ich weiß nicht, ob dies richtig ist (etwas scheint nicht richtig zu sein, ich kann es aber nicht genau sagen), aber ich glaube, es gibt einen einfacheren Weg, dies zu tun.

Bitmaske

Warum nicht einfach schreiben "Überprüfen Sie, ob erfüllt werden kann"?

\neg (Φ \equiv Ψ)

$\neg(\Phi\equiv\Psi)$

Dave Clarke

@ DaveClarke: Er definiert mit einer Quantifizierung über alle LTS, also ist nicht in der Grammatik. Allerdings scheint gut zu sein. Denkst du, es ist besser? Ich finde, meine Formulierung lässt den Leser den Unterschied zwischen Syntax und Semantik spüren, aber wen soll ich beurteilen?

\equiv

$≡$

\equiv

$≡$

\neg (Φ \Leftrightarrow Ψ)

$¬(\Phi\Leftrightarrow\Psi)$

jmad

Das von Ihnen zitierte Papier verwendet

\equiv

$\equiv$ statt des üblichen

\Leftrightarrow

$\Leftrightarrow$ Deshalb habe ich dieses Symbol verwendet. Es schien direkter zu sein als Ihre Aussage, aber wen soll ich beurteilen?

Dave Clarke

3

Wenn Sie die Identität von Hand beweisen wollen, weiß ich nicht, ob es absolut allgemeine Techniken gibt. Sie können mit den Axiomen und bekannten Identitäten für CTL beginnen und von dort aus arbeiten.

Wenn Sie die Antwort wünschen und sich Sorgen machen möchten, dass ein vom Menschen lesbarer Beweis separat vorliegt , können Sie einen CTL-Erfüllbarkeitsprüfer wie MLSolver verwenden .

Vijay D.
quelle

0

Ihr Beispiel ist nicht Äquivalenz. Nehmen Sie ein Übergangssystem mit zwei Zuständen an, die alle initial sind, und es gibt eine Schleife im Zustand, die \ phi erfüllt. Um die Gleichwertigkeit zweier CTL-Formeln zu beweisen, sollten Sie die Definition der Semantik verwenden.

rahim
quelle

-1

Könnten Sie dies in der Fixpunktcharakterisierung für CTL-Formeln ausdrücken? Das könnte Ihnen helfen, ihre Gleichwertigkeit zu beweisen. http://www-2.cs.cmu.edu/~modelcheck/ed-papers/VTfFSCS.pdf

Rohit
quelle

3

Ist das ein Kommentar / eine Anfrage oder eine Antwort?

A.Schulz

Nun, ich kenne keine Standard-Proof-Technik zum Nachweis der Äquivalenz. Es soll also eine Frage an die Community sein. Könnten wir die Fixpunktcharakterisierung verwenden, um die Äquivalenz zu beweisen?

Rohit

Dann gilt Ihre Bemerkung als Kommentar. Bitte poste es als Kommentar und lösche deine "Antwort".

A.Schulz

Wie kann ich manuell entscheiden, ob zwei CTL-Formeln gleichwertig sind?

Antworten: