Por que usar

9

Se sabe que las lógicas temporales LTL, CTL, CTL * se pueden traducir / incrustar en el cálculo . En otras palabras, el cálculo (modal) subsume estas lógicas (es decir, es más expresivo).μμ

¿Podría por favor explicarme / señalarme artículos / libros que detallen este asunto? En particular, ¿hay propiedades concretas de equidad, vitalidad, etc. que no se puedan expresar en la lógica temporal sino en el cálculo ?μ

Dimiter
fuente

Respuestas:

8

En cuanto a un μ-cálculo fórmula no expresable en CTL *, vea esta publicación .

En cuanto a los textos sobre el tema, es probable que avance más leyendo documentos, ya que estos temas no están cubiertos en muchos libros. Aún así, el Manual de la lógica modal puede ser un buen comienzo.

En cuanto a los documentos, intente:

Poder expresivo de la lógica temporal

Esta tesis doctoral

Comprobación del modelo de Emerson y el cálculo Mu

Y hay muchos más. Solo términos de google como "poder expresivo", "cálculo mu" y "lógica temporal".

Shaull
fuente
Gracias por el ejemplo y sugerencias. ¿Podría sugerir algún documento relevante? Recuerdo haber visto algunos en el pasado, pero tengo dificultades para localizarlos ahora ...
Dimiter
Se agregaron documentos a la respuesta.
Shaull
Hay un libro sobre modelado con mCRL2 ahora (para una idea aproximada de su contenido, vea el anuncio del libro ).
reinierpost
4

los μ-cálculo es estrictamente más expresivo que LTL, CTL y CTL *. Esto es consecuencia de algunos resultados diferentes.

El primer paso es demostrar que el μEl cálculo es tan expresivo como la lógica temporal. La idea principal para codificar estas lógicas proviene de reconocer las propiedades temporales como puntos fijos. En un nivel muy informal, los puntos menos fijos le permiten expresar propiedades de naturaleza finitaria y los puntos fijos más grandes se aplican a propiedades infinitas. Por ejemplo, eventualmenteφ en LTL define que hay un instante en el futuro finito en el que φes cierto, mientras que siempreφ Establece que φes cierto en un número infinito de pasos de tiempo futuros. En términos de puntos fijos, la propiedad eventualmente se expresaría usando un punto fijo mínimo y la propiedad siempre usando un punto fijo máximo. Siguiendo esa intuición, los operadores temporales pueden codificarse como operadores de punto fijo.

El siguiente paso es demostrar que el μ-El cálculo es más expresivo. La idea principal es la profundidad de alternancia. Los puntos fijos se alternan si un punto menos fijo influye en el punto fijo más grande, y viceversa. La profundidad de alternancia de unμ-la fórmula de cálculo cuenta el número de alternancias que ocurren en ella. Los operadores en CTL pueden ser codificados porμ-cálculos con profundidad de alternancia 1. Los operadores en CTL * y LTL pueden ser codificados porμ- fórmulas de cálculo con profundidad de alternancia como máximo 2. Sin embargo, la jerarquía de alternancia de laμ-cálculo es estricto, lo que significa que aumentar la profundidad de alternancia en una fórmula le permite expresar estrictamente más propiedades. Es por eso que la gente diceμEl cálculo es más expresivo que estas lógicas temporales.

Algunas referencias:

  1. Los argumentos iniciales de que el μ-cálculo subsume varias lógicas que aparecen en Modalidades para la verificación del modelo: La lógica del tiempo de ramificación contraataca , Emerson y Lei, 1985.
  2. La traducción de CTL al μ-cálculo es sencillo. Puede encontrarlo en el libro sobre Model Checking de Clarke, Grumberg y Peled. También puede encontrarlo en Model Checking y enmetrotu-cálculo de Emerson o en la disertación de Ken McMillan.
  3. La traducción de CTL * al μ-cálculo está involucrado. En lugar de la traducción indirecta original, sugiero el artículo de Mads Dam sobre la traducción de CTL * al cálculo modal modal .
  4. Hay una traducción más simple de LTL a lo que se llama el tiempo lineal μ-cálculo, en el que las modalidades operan sobre rastros y no estados. Vea Axiomatising Linear Time Mu-calculus por Roope Kaivola.
  5. La jerarquía de alternancia se estudia en La jerarquía de alternancia modal de cálculo mu es estricta por Julian Bradfield y en Un teorema de jerarquía paraμ-cálculo de Giacomo Lenzi.

Todo esto se trata de expresividad, no de utilidad. En la práctica, las personas no suelen especificar propiedades comoμ-expresiones de cálculo porque podrían encontrar lógicas temporales más fáciles de trabajar. Los lenguajes de especificación industrial difieren tanto de la lógica temporal como de laμ-cálculo en su sintaxis y su poder expresivo.

Vijay D
fuente
Gracias por una gran respuesta! Con respecto a su comentario sobre la utilidad: suponga que quiero usar un verificador de modelo de cálculo μ, pero especifique cosas en lógicas temporales, lo cual es más fácil. ¿Existe una técnica (aún mejor, una herramienta) que traduzca automáticamente las fórmulas en cualquiera de estas lógicas (CTL, CTL * o LTL) al cálculo μ? ¡Gracias!
Dimiter
SMV traduce internamente CTL en μ-cálculo. No estoy seguro de qué herramienta explícitamente hace esto.
Vijay D
2

Es bien sabido que μ-calculi puede expresar propiedades que "cuentan módulo a constante", por ejemplo, " todos los pasos pares visitan unUNA-state "que es capturado por algo comoμX.UNAX. Dichas propiedades no se pueden establecer con las modalidades TL estándar Hasta y Siguiente, ya que estas modalidades son definibles de primer orden. Ver el artículo de 1983 de DC Kozen .

phs
fuente