Intuitive Bedeutung von modal $ mu $ -Calculus-Formel

Question

Ich löste eine der früheren Prüfungen und bin mir nicht sicher, wie meine Lösung für eine der Übungen. Die Übung bittet darum, der modalen $ mu $ -Calculus-Formel eine intuitive Bedeutung zu geben:

$$ phi = mu z. Langle - rangle tt kedge [-a] z $$

Nach einem Artikel Modale Logik und Mu-Calculi: Eine Einführung von Bradfield und Stirling [1] die Intuition hinter $ mu $ operator ist "Endliche Schleife". Meine Argumentation folgt also: Auf jedem Weg durch Staaten in $ z $ muss es nur eine begrenzte Anzahl von Übergängen mit Etiketten von $ a $ geben, und dann müssen wir einen Staat erreichen, der beide nicht terminal ist (von Anfang an Bedingung) und alle Übergänge daraus werden als $ a $ (aus Endlichkeit) bezeichnet.

Daher muss auf jedem Weg durch Staaten $ z $ letztendlich einen Übergang mit $ $ $ geben. (Ähnlich wie die CTL -Formel $ forall f (a) $).

Ist meine Argumentation korrekt? Ich kann keinen formellen Grund für meine Lösung finden, um richtig zu sein. Können Sie mir einen kleinen Hinweis geben?

[1] http://homepages.inf.ed.ac.uk/jcb/research/bradfield-stirling-hpa-mu-intro.ps.gz

Answer 1

Lass es uns zusammenbrechen.

Schauen wir uns zunächst $ [-A] Phi $ an. Dies bedeutet, dass jeder nicht $ a $ $ zu einem Staat führt, in dem $ phi $ hält. Daraus folgt, dass $ [-A] mathhrm {ff} $ für Staaten gilt, die keine Übergänge von $ a $ haben, die wir bei der Betrachtung der am wenigsten festen Punktsemantik verwenden werden.

$ langle- rangle mathhrm {tt} $ ist ziemlich einfach. Es gilt in jedem Zustand, der einen Übergang hat, dh nicht abgestimmt.

Also zusammen $ Langle- rangle mathrm {tt} land [-a] phi $ bedeutet, dass der Staat einen Übergang durchführen kann und $ phi $ nach jedem Nicht-$-Übergang hält.

Eine Möglichkeit, die Bedeutung von $ mu z. phi (z) $ anzuzeigen, ist die Annäherungen, auf die in Ihrem verknüpften Tutorial verwiesen wird. Wenn die Formel im Zustand $ s $ erfüllt ist, gibt es einige $ beta $ so, dass $ bigvee _ { alpha < beta} phi^{( alpha)} ( mathrm {ff}) $ erfüllt in erfüllt in $ s $. Die Notation $ phi^{(n)} (x) $ bedeutet $ phi $ iteriert auf $ x $, $ n $ mal, dh $ Underbrace { phi ( phi ( dots phi (x)) )} _ { text {$ n $ mal}} $. Schauen wir uns einige davon an.

begin {align} phi^{(0)} ( mathrm {ff}) & = mathhrm {ff} phi^{(1)} ( mathem {ff}) & = langle- Rangle mathhrm {tt} land [-a] phi^{(0)} ( mathrm {ff}) & = Langle- rangle mathem {tt} land [-a] mathrm {{mathrm {tt} land [-a] mathrm {{mathem math ff} phi^{(2)} ( mathrm {ff}) & = Langle- rangle mathrm {tt} land [-a] phi^{(1)} ( mathrm {ff }) & = Langle- rangle mathrm {tt} land [-a] ( Langle- rangle mathrm {tt} land [-a] mathrm {ff}) phi^^ {(3)} ( mathrm {ff}) & = Langle- rangle mathrm {tt} land [-a] phi^{(2)} ( mathrm {ff}) & = Langle- mathrm {ff})) end {align}

Hoffentlich ist klar, dass diese die Bedeutungen haben

1. $ phi^{(1)} ( mathhrm {ff}) $: Staaten, die nur $ a $ übergingen können
2. $ phi^{(2)} ( mathhrm {ff}) $: Live gibt an
   1. haben nur $ a $ wechsel; oder
   2. Alle Länge 1 Nicht $-$-Pfade führen zu einem Live-Staat mit nur $ a $ wechsel
3. $ phi^{(3)} ( mathhrm {ff}) $: Live gibt an
   1. haben nur $ a $ wechsel; oder
   2. Alle Länge 1 Nicht $-$-Pfade führen zu einem Live-Staat mit nur Übergängen $ A $; oder
   3. Alle Länge 2 Nicht-$-Pfade führen zu einem Live-Staat mit nur $ a $ wechsel

Wenn dies unklar ist, denken Sie daran, dass $ [-A] Phi $ für Staaten ohne Übergang ohne $ a $ trivial zufrieden ist.

Jetzt sollten Sie sehen, dass $ phi^{(n)} ( mathrm {ff}) $ gilt, wenn der Staat höchsten mit nur $ a $ wechsel. Es stellt sich heraus mit geringeren Annähern und kann einfach sagen $ mu z. langle- phi^{( beta)} ( mathrm {ff}) $ oder in englischer Sprache nach einer endlichen Anzahl von Nicht-$-Übergängen, die wir mit nur $ A $ über eine Übergänge erreichen.