モーダル$ mu $ -calculus式の直感的な意味

Question

私は過去の試験の1つを解決していますが、演習の1つに対する解決策が確かではありません。この演習では、モーダル$ mu $ -calculus式に直感的な意味を与えることを求めています。

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

記事によると モーダルロジックとMU-calculi：はじめに Bradfield and Stirling [1] $ mu $オペレーターの背後にある直観は "有限ループ"。だから私の推論は次のとおりです。$ z $の状態を通るすべてのパスでは、$ a $とは異なるラベルを持つ有限数の遷移しかなければなりません。その後、両方とも非末端（最初から）に到達する必要があります。条件）およびそこからのすべての遷移には、$ a $（FIN FINNESS）とラベル付けされています。

したがって、$ z $の状態を通るすべてのパスでは、最終的に$ a $というラベルが付いた遷移がなければなりません。 （CTLフォーミュラ$ forall f（a）$に似ています）。

私の理由は正しいですか？私の解決策が正しい理由を見つけることができません、あなたは私に少しヒントを与えてくれませんか？

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

Answer 1

それを分解しましょう。

まず、$ [a] phi $を見てみましょう。これは、すべての非$ A $の移行が$ phi $が保持する状態につながることを意味します。その場合、$ [a] mathrm {ff} $は、$ a $の遷移がない状態に対して保持されます。

$ langle- rangle mathrm {tt} $は非常に簡単です。移行がある州には、つまりデッドロックされていません。

一緒に$ langle- rangle mathrm {tt} land [-a] phi $は、状態が遷移を取ることができることを意味し、$ a $ a $の移行ごとに$ phi $が保持されることを意味します。

$ mu z. phi（z）$の意味を表示する1つの方法は、リンクされたチュートリアルで参照されている近似によって行われます。式が状態$ s $で満たされている場合、$ bigvee _ { alpha < beta} phi^{（ alpha）}（ mathrm {ff}）$が満たされるような$ beta $があります。 $ s $。表記$ phi^{（n）}（x）$は、$ x $、$ n $ timesで$ phi $を意味します。 ）} _ { text {$ n $ times}} $。これらのいくつかを見てみましょう。

begin {align} phi^{（0）}（ mathrm {ff}）＆= mathrm {ff} phi^{（1）}（ mathrm {ff}）＆= langle- rangle mathrm {tt} land [-a] phi^{（0）}（ mathrm {ff}）＆= langle- rangle mathrm {tt} land [-a] mathrm { ff} phi^{（2）}（ mathrm {ff}）＆= langle- rangle mathrm {tt} land [-a] phi^{（1）}（ mathrm {ff 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- rangle mathrm {tt} land [-a]（ langle- rangle mathrm {tt} land [-a]（ langle- rangle mathrm {tt} land [-a] Mathrm {ff}）） end {align}

これらが意味を持っていることが明らかになることを願っています

1. $ phi^{（1）}（ mathrm {ff}）$：$ a $ transitionsのみを取ることができる状態
2. $ phi^{（2）}（ mathrm {ff}）$：live stase
   1. $ a $の移行のみがあります。また
   2. すべての長さ1非$ a $パスは、$ a $の移行のみでライブ状態につながります
3. $ phi^{（3）}（ mathrm {ff}）$：liveはそのような状態
   1. $ a $の移行のみがあります。また
   2. すべての長さ1以外の$ a $パスは、$ a $の移行のみでライブ状態につながります。また
   3. すべての長さ2非$ a $パスは、$ a $のトランジションだけでライブ状態につながります

それが不明な場合は、$ [a] phi $は、$ a $の遷移なしで州に対して簡単に満たされていることを忘れないでください。

これで、$ phi^{（n）}（ mathrm {ff}）$は、ライブ状態に到達する前に$ n-1 $ n-1 $ non $ a $を取得できる場合にのみ真実であることがわかります。 $ a $のトランジションだけがあります。 $ phi^{（n）}（ mathrm {ff}）は、 phi^{（n+1）}（ mathrm {ff}）$を暗示する必要はありません。より少ない近似で、$ mu z. langle- rangle mathrm {tt} land [-a] z iff exists beta in mathbb {n}と言うことができます。 phi^{（ beta）}（ mathrm {ff}）$、または英語で、有限数の非$ a $遷移の後、$ a $の移行のみでライブ状態に到達します。