CTL * y cálculo mu

9

es bien sabido que el cálculo μ modalμ es una de las lógicas temporales más expresivas para expresar las propiedades de los árboles / gráficos, y que CTL * es estrictamente menos expresivo que el cálculo .μ

Aquí me gustaría pedir un ejemplo de fórmula de cálculo , tan simple como sea posible, que no se pueda expresar en CTL *, y con suerte una explicación de su significado (las fórmulas de punto fijo se vuelven rápidamente ilegibles). ¡Cualquier buena referencia para un ejemplo simple "concreto" también sería genial!μ

Gracias de antemano

LORE81
fuente

Respuestas:

11

Tome una propiedad de ruta que no sea de primer orden, por ejemplo, que dice que existe un camino donde la proposición atómica p

νX.pagsX
pags mantiene en cada posición par, y cualquier valoración puede usarse en posiciones impares.
Sylvain
fuente
Muchas gracias por esta simple respuesta. ¿Podría sugerir también una referencia que respalde este ejemplo? Gracias de nuevo
LORE81
Buena pregunta y respuesta (+2). Eche un vistazo a cstheory.stackexchange.com/q/16186/6424 . Di el ejemplo de la uniformidad allí también. Quizás alguna respuesta también se refiera a la uniformidad.
DaveBall aka user750378
@ LORE81: el ejemplo de `` en posiciones pares '' es un clásico, que puedes encontrar, por ejemplo, en el artículo de Wolper señalado por @DaveBall en su pregunta. No es demasiado difícil probar directamente por inducción en fórmulas LTL; alternativamente, puede construir el monoide de transición y ver que no es aperiódico; finalmente puede probar un argumento de Ehrenfeucht-Fraïssé, aunque es largo explicarlo en detalle. p
Sylvain