sintaxis ctl.pdf

Download Sintaxis CTL.pdf

Post on 27-Oct-2015

55 views

Category:

Documents

3 download

Embed Size (px)

TRANSCRIPT

  • Sintaxis de CTL

    Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

  • Sintaxis de CTL

    2 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    Contenido Contenido ............................................................................................................................... 2

    1. Sintaxis ............................................................................................................................... 3

    2. Semntica ........................................................................................................................... 4

    3. Equivalencia de frmulas CTL ........................................................................................... 8

    4. Formas Normales para CTL ............................................................................................. 10

    5. Referencias ....................................................................................................................... 12

  • Sintaxis de CTL

    3 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    1. Sintaxis

    CTL tiene una sintaxis de dos etapas donde las formulas en CTL son clasificadas en

    frmulas de estado y de camino. Las frmulas de estado son aserciones sobre una proposicin

    atmica en los estados y su estructura de enramado, mientras que las frmulas de camino

    expresan propiedades temporales en los caminos.

    Definicin 6.1 Sintaxis de CTL

    Las frmulas de estado CTL sobre un conjunto de proposiciones atmicas estn formadas de acuerdo a la siguiente gramtica:

    = | | 1 2 | | |

    Donde y es una frmula de camino. Las frmulas de camino CTL estn formadas de acuerdo a la siguiente gramtica:

    = | 1 2

    Donde , 1, 2 son frmulas de estado.

    Para diferenciar frmulas de estado y frmulas de camino, las primeras se escribirn

    con letras griegas maysculas y las segundas con letras griegas minsculas. Las frmulas de

    estado expresan propiedades de estado, mientras que las segundas expresan propiedades del

    camino. El operador temporal representa que una propiedad debe cumplirse en el siguiente estado del camino, mientras que el operador representa que la 1 debe cumplirse hasta que la propiedad 2 se cumpla. Los operadores que cuantifican los caminos preceden a los operadores temporales. El cuantificador nos indica que la frmula de camino tiene que cumplirse en algn camino desde el estado actual, mientras que el cuantificador nos dice que cada camino debe cumplir la frmula de camino.

    Los operadores Booleanos , , , y se definen de la forma usual, mientras que las modalidades temporales se pueden derivar de la siguiente manera:

    Formula Descripcin

    = ( ) Potencialmente se mantiene = ( ) Es inevitable que

    = Potencialmente siempre = Invariantemente

  • Sintaxis de CTL

    4 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    2. Semntica

    Las frmulas de CTL son interpretadas sobre los estados y caminos de un sistema de

    transiciones . Formalmente, dado un sistema de transiciones , las semnticas de las formulas CTL estn definidas por dos relaciones de satisfaccin: Una para las frmulas de

    estado y otras para las frmulas de caminos. La primera relacin es entre los estados en y una formula de estado: , esto es, se mantiene en el estado . La segunda relacin es entre un fragmento de camino mximo en y una frmula de camino: , esto es el camino satisface la formula .

    Definicin 6.4

    Sea una proposicin atmica, = (, , , , , ) un sistema de transiciones sin estados terminales, , , formulas CTL de estados, y una formula CTL de camino. La relacin de satisfaccin est definida para frmulas de estados por:

    Formula Condicin

    () No se cumple ( ) y ( ) para algn () para todo ()

    Para caminos , la relacin de satisfaccin para caminos est definida por:

    Formula Condicin

    [1] 0, ( [] (0 < , [] ))

    Donde para el camino = 012 y enteros 0, [] denota el estado ( + 1)-esimo de , es decir, [] = .

    Definicin 6.5

    Dado un sistema de transiciones , el conjunto de satisfaccin (), para una formula CTL de estados esta definido por:

    () = { | }

    El sistema de transiciones satisface la formula CTL si y solo si se mantiene en todos los estados iniciales de :

  • Sintaxis de CTL

    5 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    0 , 0

    Esto es equivalente a ().

    Otras semnticas tiles de CTL son las siguientes:

    Formula Condicin

    (), [] para todo 0. (), [] para todo 0. (), [] para algn 0. (), [] para algn 0.

    Ilustracin 1: Visualizacin de la semntica de algunas frmulas bsicas de CTL1

    1 Ilustracin tomada de [1].

  • Sintaxis de CTL

    6 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    La ilustracin 1 visualiza grficamente en qu consisten varias de estas frmulas,

    siendo de color negro los estados que satisfacen la proposicin y grises los que satisfacen la proposicin .

    Observacin 6.8 Frecuencia Infinita

    Es cuando un estado es visitado una cantidad de veces infinita dentro de un camino.

    Esto sirve para comprender la siguiente proposicin y formula de CTL:

    si y solo si (), [] para una cantidad infinita.

    Observacin 6.9 Weak Until

    Es un operador de camino denotado por . La intuicin en este operador es que un camino satusface , para las frmulas de estado y , si se cumple cualquiera de o . La diferencia con el operador Until () es que no requiere ser alcanzada eventualmente. En lgica CTL, este operador se define de la

    siguiente manera:

    ( ) = (( ) ( ))

    ( ) = (( ) ( ))

    Observacin 6.10 La semntica de la negacin

    Para un estado , tenemos que si y solo si , sin embargo, esto no se mantiene en general para un sistema de transiciones. Podemos tener enunciados para

    los cuales se cumpla tanto que como que . Esto se debe a que podemos tener dos estados iniciales, 0 y 0, tal que 0 y 0 . Por lo tanto:

    si y solo si existe un camino () con .

    Esta equivalencia es justificada por el hecho de que la interpretacin de una formula

    CTL de estados sobre un sistema de transiciones est basada en una cuantificacin

    universal sobre los estados iniciales. Por otro lado, requiere que 0 sobre todos los 0 .

    Observacin 6.11 Semntica CTL para Sistemas de Transiciones con estados

    Terminales

    Para un fragmento de camino mximo finito = 012 de longitud , con como estado terminal, sea:

    Formula Condicin

    > 0 y 1 . Existe un ndice con y , para

    = 0,1,2 , 1 y

  • Sintaxis de CTL

    7 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    Entonces, si y solo si es un estado terminal. Por los operadores derivados y obtenemos que

    Formula Condicin

    Existe un ndice con

    Para todo con tenemos que

  • Sintaxis de CTL

    8 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    3. Equivalencia de frmulas CTL

    Ilustracin 2: Algunas reglas de equivalencia para CTL2

    2 Ilustracin tomada de [1].

  • Sintaxis de CTL

    9 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com

    Las formulas CTL y se dice que son equivalentes siempre que estas sean semnticamente idnticas, esto es, cualquier estado mantendr que si y solo si .

    Definicin 6.12 Equivalencia de frmulas CTL

    Las formulas CTL y (sobre ) se dice que son equivalentes, denotado por , si () = () para todos los sistemas de transicin sobre .

    Incluyendo todas las reglas de equivalencia estndar para la los fragmentos de lgica

    proposicional en CTL, tambin existen reglas de equivalencia para reglas con modalidades

    temporales en CTL, descritas varias en la ilustracin 2.

    En CTL, tenemos reglas de expansin para ( ) y para ( ). En el caso de ( ), esta expresin es equivalente al hecho de que el estado actual satisface , o este satisface , y para algn estado sucesor directo, ( ) se mantiene. La regla de expansin para y puede ser simplemente derivadas de las reglas de expansin para . La idea bsica detrs de estas reglas es expresar la valides de una formula por medio de un predicado sobre el estado actual y un predicado sobre los sucesores directos de este

    estado. Por ejemplo, es valida en el estado si es valido en (un predicado sobre el estado actual) y se mantiene por todos los caminos a travs de un camino que empiece de (un predicado sobre los estados sucesores).

    La expresin ( ) es equivalente a , sin embargo las expresiones ( ) y no son equivalentes. Esto debido a que la primera expresin obliga a que alguna de las dos, o , se cumplan dentro del mismo camino, mientras que la segunda solo obliga a que se cumpla alguna de esas dos frmulas CTL, no

    importa si estn en caminos diferentes.

  • Sintaxis de CTL

    10 Ulises Martinez Araiza

    umartinez@gdl.cinvestav.mx

    www.ulisesmartinez.com