significato intuitivo di $ modale \ mu $ -calcolo formula

Question

sto risolvendo uno degli esami passati e io non sono certo con la mia soluzione ad uno degli esercizi. L'esercizio chiede di dare un senso intuitivo da modale $ \ mu $ -calcolo formula:

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

Secondo un articolo logiche modali e mu-calcoli: un'introduzione di Bradfield e Stirling [1] l'intuizione dietro $ \ mu $ operatore è " finito looping " . Quindi il mio ragionamento è il seguente: su ogni percorso attraverso stati di $ Z $ ci deve essere solo un numero finito di transizioni con etichette differenti da $ a $ e dobbiamo raggiungere uno stato che è sia non-terminale (dalla prima condizione) e tutte le transizioni da esso sono etichettati $ a $ (da finitezza).

Quindi su ogni percorso attraverso Uniti in $ Z $ ci deve alla fine essere una transizione etichettata $ A $. (Simile a CTL formula $ \ forall a) $ F ().

E 'il mio ragionamento è corretto? Sono in grado di trovare alcuna ragione formale per la mia soluzione di avere ragione, mi puoi dare un piccolo suggerimento?

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

Answer 1

pausa di che lascia a desiderare.

In primo luogo, Diamo un'occhiata a $ [- a] \ phi $. Questo significa che ogni non-$ A $ derivazioni di transizione a uno stato in cui $ \ phi $ detiene. Ne consegue che $. [- a] \ mathrm {FF} $ vale per gli Stati che non hanno mancato $ A $ transizioni, che useremo quando guardando la semantica punto almeno fisse

$ \ langle- \ rangle \ mathrm {TT} $ è piuttosto semplice. Si tiene in qualsiasi stato che ha qualsiasi transizione, cioè non è in stallo.

Così insieme $ \ langle- \ rangle \ mathrm {} tt \ terra [-a] \ phi $, lo Stato può prendere una transizione e $ \ phi $ detiene dopo ogni non- $ a $ di transizione.

Un modo per vedere il significato di $ \ mu Z. \ phi (Z) $ è dalle approssimanti riferimento nel tuo tutorial collegato. Se la formula è soddisfatto in stato di $ s $ allora c'è qualche $ \ beta $ tale bigvee che $ \ _ {\ alpha <\ beta} \ phi ^ {(\ alpha)} (\ mathrm {FF}) $ è soddisfatta in $ s $. La notazione $ \ phi ^ {(n)} (x) $ mezzo $ \ $ phi iterato su $ x $, $ n $ volte, vale a dire $ \ underbrace {\ phi (\ phi (\ dots \ phi (x)) )} _ {\ text {$ n $ volte}} $. Diamo un'occhiata ad alcuni di questi.

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

Si spera, è chiaro che questi hanno i significati

1. $ \ phi ^ {(1)} (\ mathrm {} ff) $: Stati che può assumere solo $ un transizioni
$
2. $ \ phi ^ {(2)} (\ mathrm {} ff) $: live afferma che
   1. hanno solo $ A $ transizioni; o
   2. tutta la lunghezza 1 non- $ A $ percorsi conducono a uno stato vivo con solo $ un transizioni
   $
3. $ \ phi ^ {(3)} (\ mathrm {} ff) $: live afferma che
   1. hanno solo $ A $ transizioni; o
   2. tutta la lunghezza 1 non $ sentieri conducono ad uno stato vivo con solo $ a $ transizioni di $; o
   3. tutta la lunghezza 2 non $ A $ percorsi conducono a uno stato vivo con solo $ un transizioni
   $

Se questo non è chiaro, ricordate che $ [- a]. \ Phi $ è banalmente soddisfatta per gli stati senza non- $ A $ transizioni

Ora si dovrebbe vedere che $ \ phi ^ {(n)} (\ mathrm {} ff) $ è vero se e solo se lo stato può assumere al massimo $ n-1 $ non $ a $ transizioni prima di raggiungere uno stato vivo con solo $ a $ transizioni. Si scopre che $ \ phi ^ {(n)} (\ mathrm {} ff) \ implica \ phi ^ {(n + 1)} (\ mathrm {} ff) $ quindi non abbiamo bisogno di prendere la disgiunzione con approssimanti minori e può semplicemente dire $ \ mu Z. \ langle- \ rangle \ mathrm {} tt \ terra [-a] Z \ se e solo se \ esiste \ beta \ in \ mathbb {N}. \ Phi ^ {(\ beta)} (\ mathrm {FF}) $, o in inglese, dopo un numero finito di non $ A $ transizioni si raggiunge uno stato di tensione con soli $ A $ transizioni.