Intuitive sens de $ modal \ mu $ -calcul formule

Question

Je résolvait un des examens passés et je ne suis pas certain de ma solution à l'un des exercices. L'exercice demande de donner un sens intuitif modal $ \ mu $ -calcul formule:

$$ \ phi = \ mu Z. \ langle - \ rangle tt \ wedge [-a] Z $$

D'après un article Logiques modales et mu-lithiase: une introduction par Bradfield et Stirling [1] l'intuition derrière $ \ mu $ opérateur est " fini looping " . Donc, mon raisonnement est le suivant: sur tous les chemins par des états $ Z $ il doit y avoir un nombre fini de transitions avec des étiquettes différentes de $ a $ et nous devons atteindre un état qui est à la fois non-terminale (de la première condition) et toutes les transitions de celui-ci sont étiquetés $ a $ (de finitude).

Par conséquent sur tous les chemins par des états $ Z $, il doit éventuellement être une transition étiquetée $ a $. (Similaire à la formule CTL $ \ forall F (a) $).

Mon raisonnement correct? Je suis incapable de trouver une raison formelle pour ma solution soit droite, pouvez-vous me donner un petit indice?

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

Answer 1

pause Let vers le bas.

Tout d'abord, le regard let à $ [- a] \ phi $. Cela signifie que chaque transition non $ a $ conduit à un état où $ \ phi détient $. Il en découle que $. [- a] \ mathrm {ff} $ est valable pour les États qui n'ont pas non transitions $ $ une, que nous utiliserons lors de la recherche à la sémantique des points moins fixes

$ \ langle- \ rangle \ mathrm {tt} $ est assez simple. Il contient en tout état qui a toute transition, à savoir est pas dans l'impasse.

Alors, ensemble $ \ langle- \ rangle \ mathrm {tt} \ terre [-a] \ phi moyens $ l'État peut prendre une transition et $ \ phi $ tient après chaque non $ une transition $.

Une façon de voir la signification de $ \ mu Z. \ phi (Z) $ est par les approximants référencés dans votre tutoriel lié. Si la formule est satisfaite dans l'état $ s $, alors il est un peu $ \ beta $ tel que $ \ bigvee _ {\ alpha <\ beta} \ phi ^ {(\ alpha)} (\ mathrm {ff}) $ est satisfaite dans $ de $ s. La notation $ \ phi ^ {(n)} (x) $ moyen $ \ phi $ itérer sur $ x $, $ n fois $, soit $ \ underbrace {\ phi (\ phi (\ points \ phi (x)) )} _ {\ texte {$ n $ fois}} $. Regardons à certains d'entre eux.

\ begin {align} \ Phi ^ {(0)} (\ mathrm {} ff) & = \ mathrm {} ff \\ \ Phi ^ {(1)} (\ mathrm {} ff) & = \ langle- \ rangle \ mathrm {tt} \ terre [-a] \ phi ^ {(0)} (\ mathrm {} ff) \\ & = \ Langle- \ rangle \ mathrm {tt} \ terre [-a] \ mathrm {ff} \\ \ Phi ^ {(2)} (\ mathrm {} ff) & = \ langle- \ rangle \ mathrm {tt} \ terre [-a] \ phi ^ {(1)} (\ mathrm {} ff) \\ & = \ Langle- \ rangle \ mathrm {tt} \ terre [-a] (\ langle- \ rangle \ mathrm {tt} \ terre [-a] \ mathrm {} ff) \\ \ Phi ^ {(3)} (\ mathrm {} ff) & = \ langle- \ rangle \ mathrm {tt} \ terre [-a] \ phi ^ {(2)} (\ mathrm {} ff) \\ & = \ Langle- \ rangle \ mathrm {tt} \ terre [-a] (\ langle- \ rangle \ mathrm {tt} \ terre [-a] (\ langle- \ rangle \ mathrm {tt} \ terre [- a] \ mathrm {} ff)) \ End {align}

Si tout va bien, il est clair que ceux-ci ont les significations

1. $ \ phi ^ {(1)} (\ mathrm {} ff) $: les États qui ne peuvent prendre que $ une transition $
2. $ \ phi ^ {(2)} (\ mathrm {} ff) $: en direct que les États
   1. ont seulement $ transitions $ a; ou
   2. toute la longueur 1 $ non des sentiers de $ conduisent à un état en temps réel avec seulement $ une transition $
3. $ \ phi ^ {(3)} (\ mathrm {} ff) $: en direct que les États
   1. ont seulement $ transitions $ a; ou
   2. 1 toute la longueur non $ a $ chemins mènent à un état en temps réel avec seulement $ transitions $ un; ou
   3. toute la longueur 2 $ non des sentiers de $ conduisent à un état en temps réel avec seulement $ une transition $

Si tel est peu clair, rappelez-vous que $ [- a]. \ Phi $ est trivialement satisfaite pour les États non sans transitions $ $ a

Maintenant, vous devriez voir que $ \ phi ^ {(n)} (\ mathrm {ff}) $ est vrai si et seulement si l'État peut prendre au maximum $ n-1 $ non $ a $ transition avant d'atteindre un état en temps réel avec seulement $ transitions $ a. Il se trouve que $ \ phi ^ {(n)} (\ mathrm {ff}) \ implique \ phi ^ {(n + 1)} (\ mathrm {} ff) $ donc on n'a pas besoin de prendre la disjonction avec moins approximants et peut simplement dire $ \ mu Z. \ langle- \ rangle \ mathrm {tt} \ terre [-a] Z \ ssi \ existe \ beta \ in \ mathbb {N}. \ Phi ^ {(\ beta)} (\ mathrm {ff}) $, ou en anglais, après un nombre fini de non $ une transition de $, nous atteignons un état en temps réel avec seulement $ une transition de $.