Significado intuitivo de la fórmula de cálculo modal $\mu$

Question

Estoy resolviendo uno de los exámenes anteriores y no estoy seguro de mi solución a uno de los ejercicios.El ejercicio pide dar un significado intuitivo a la fórmula de cálculo modal $\mu$:

$$ \phi = \mu Z.\langle - angle tt \cuña [-a]Z $$

Según un artículo Lógicas modales y mu-cálculos:una introducción por Bradfield y Stirling[1] la intuición detrás del operador $\mu$ es "bucle finito".Entonces mi razonamiento es el siguiente:en cada camino a través de estados en $Z$ debe haber solo un número finito de transiciones con etiquetas diferentes de $a$ y luego debemos alcanzar un estado que sea no terminal (desde la primera condición) y todas las transiciones desde él sean etiquetado como $a$ (de finitud).

Por lo tanto, en cada camino a través de estados en $Z$ eventualmente debe haber una transición denominada $a$.(similar a la fórmula CTL $\forall F(a)$).

¿Es correcto mi razonamiento?No puedo encontrar ninguna razón formal para que mi solución sea correcta, ¿puede darme una pequeña pista?

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

Answer 1

Vamos a desglosarlo.

Primero, veamos $ [-a] phi $. Esto significa que cada transición no $ A $ conduce a un estado donde $ phi $ se mantiene. Se deduce entonces que $ [-a] mathrm {ff} $ se mantiene para los estados que no tienen transiciones no $ a $, que usaremos al mirar la semántica de punto menos fijo.

$ langle- rangle mathrm {tt} $ es bastante simple. Se mantiene en cualquier estado que tenga alguna transición, es decir, no está bloqueado.

Entonces, juntos $ langle- rangle mathrm {tt} land [-a] phi $ significa que el estado puede tomar una transición y $ phi $ retiene después de cada transición sin $ a $.

Una forma de ver el significado de $ mu z. phi (z) $ es por los aproximantes a los que se hace referencia en su tutorial vinculado. Si la fórmula está satisfecha en el estado $ S $, entonces hay unos $ beta $ tal que $ bigVee _ { alpha < beta} phi^{( alpha)} ( mathrm {ff}) $ está satisfecho en $ S $. La notación $ phi^{(n)} (x) $ significa $ phi $ iterated en $ x $, $ n $ veces, es decir, $ subbacial { phi ( phi ( dots phi (x)) )} _ { text {$ n $ Times}} $. Veamos algunos de estos.

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 }) & = 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}

Ojalá esté claro que estos tienen los significados

1. $ phi^{(1)} ( mathrm {ff}) $: Estados que solo pueden tomar $ A $ transiciones
2. $ phi^{(2)} ( mathrm {ff}) $: Live afirma que
   1. tienen solo $ A $ transiciones; o
   2. Toda la duración 1 no $ a $ rutas conducen a un estado en vivo con solo $ A $ transiciones
3. $ phi^{(3)} ( mathrm {ff}) $: Live afirma que
   1. tienen solo $ A $ transiciones; o
   2. Todas las rutas no $ A $ no conducen a un estado en vivo con solo $ A $ transiciones; o
   3. Todas las rutas de duración 2 no $ a $ conducen a un estado en vivo con solo $ A $ transiciones

Si eso no está claro, recuerde que $ [-a] phi $ está trivialmente satisfecho para los estados sin transiciones no $ a $.

Ahora debería ver que $ phi^{(n)} ( mathrm {ff}) $ es verdadero si y solo si el estado puede tomar como máximo $ n-1 $ no $ a $ transiciones antes de llegar a un estado en vivo con solo $ A $ transiciones. Resulta que $ phi^{(n)} ( mathrm {ff}) implica phi^{(n+1)} ( mathrm {ff}) $ para que no necesitemos tomar la disyunción con aproximantes menores y simplemente puede decir $ mu z. langle- rangle mathrm {tt} land [-a] z iff existe beta in mathbb {n}. Phi^{( beta)} ( mathrm {ff}) $, o en inglés, después de un número finito de transiciones no $ a $, llegamos a un estado en vivo con solo $ a $ transiciones.