Visualising CTL Witnesses and Counterexamples -- Extended Version

Aquí presento un resumen técnico detallado del artículo "Visualising CTL Witnesses and Counterexamples — Extended Version" de Arend Rensink, traducido y estructurado en español.

1. Planteamiento del Problema

El artículo aborda una brecha fundamental en la verificación de modelos (model checking) entre dos lógicas temporales principales: LTL (Lógica Temporal Lineal) y CTL (Lógica Temporal de Árbol de Computación).

• El problema con LTL: En LTL, si una propiedad no se cumple, es fácil generar y visualizar un contraejemplo: una única traza (secuencia lineal de estados) que viola la propiedad. Esto es intuitivo para los humanos.
• El problema con CTL: CTL maneja estructuras de tiempo "ramificadas". La no satisfacción de una propiedad CTL no puede explicarse simplemente por una traza lineal, ya que la lógica depende de la estructura de ramificación completa (existencia o universalidad de caminos).
• La dificultad actual: En CTL, no existe una noción simple de contraejemplo. Además, la negación de una propiedad CTL satisfecha no siempre es trivial de visualizar como un contraejemplo directo debido a la dualidad de los operadores.
• Objetivo: Definir una noción unificada de evidencia (que sirva tanto como testigo para propiedades satisfechas como contraejemplo para las violadas) que capture la razón mínima de la satisfacción o violación de una fórmula CTL, y desarrollar métodos para visualizarla de manera comprensible para humanos.

2. Metodología

El autor propone un marco formal basado en modelos explícitos de estados y introduce conceptos novedosos para manejar la complejidad de la lógica ramificada.

A. Definiciones Formales

• Modelos y Submodelos: Se define un modelo $M = \langle S, C, R, L \rangle$, donde $S$ son estados, $R$ es la relación de transición, $L$ es una función de etiquetado parcial, y crucialmente, $C \subseteq S$ es un conjunto de estados cerrados.
• Estados Cerrados ($C$): Un estado es "cerrado" si no tiene transiciones salientes en el submodelo actual, pero sí las tiene en el modelo original. Esto es vital para representar contraejemplos: si un estado está cerrado, garantiza que ningún supermodelo puede añadir transiciones que satisfagan la propiedad.
• Evidencia: Se define como un submodelo suficiente para probar la veracidad o falsedad de una afirmación (estado, fórmula, valor booleano).
  • Testigo (Witness): Evidencia para una afirmación verdadera ($b=1$).
  • Contraejemplo (Counterexample): Evidencia para una afirmación falsa ($b=0$).
• Minimalidad: Se busca la evidencia más pequeña (en términos de submodelos) que aún sea suficiente para probar la afirmación.

B. Caracterización de la Evidencia

El artículo clasifica las condiciones necesarias y suficientes para que un modelo sea una evidencia mínima para los operadores temporales clave de CTL:

• Operadores Existenciales (EX, EU, EG):
  • Para EX $\psi$: Basta con una transición a un estado que satisfaga $\psi$.
  • Para E $\psi_1$ U $\psi_2$: Se requiere un único camino finito de estados abiertos donde $\psi_1$ se cumple hasta que $\psi_2$ se cumple en el último estado.
  • Para EG $\psi$: Se requiere un camino (finito que termina en estado cerrado, o infinito) donde $\psi$ se cumple siempre.
• Operadores Universales (AX, AU, AG): Se tratan mediante la dualidad (negación de los existenciales), donde los estados cerrados juegan un papel crucial para demostrar que todos los caminos posibles fallan.

C. Visualización y Pruebas

• Pruebas (Proofs): Una prueba es un mapeo que asigna a cada par (estado, subfórmula) su evidencia correspondiente.
• Evidencia Natural: Se introduce este concepto para mejorar la legibilidad. Una evidencia "mínima" formal puede omitir información local (ej. no etiquetar subfórmulas en estados intermedios), lo cual es confuso para humanos. La "evidencia natural" incluye la información de satisfacción de todos los hijos en estados no terminales, haciendo la explicación más intuitiva.
• Evidencia Combinada: Se demuestra que es posible combinar las evidencias para una fórmula fija a través de todos los estados en un único modelo, reduciendo la complejidad visual de mostrar múltiples instantáneas.

3. Contribuciones Clave

1. Modelo Formal de Evidencia: La definición rigurosa de evidencia para CTL que unifica testigos y contraejemplos, introduciendo el concepto de estados cerrados para capturar la ausencia de transiciones necesarias en contraejemplos.
2. Caracterización de Minimalidad: Se proporcionan condiciones sintácticas y semánticas (Tablas 1 y 2 en el artículo) que definen exactamente qué constituye una evidencia mínima para cada operador temporal.
3. Noción de Evidencia Natural: Una mejora pragmática sobre la minimalidad formal estricta, diseñada específicamente para la comprensión humana, rellenando información local que, aunque técnicamente redundante, es cognoscitivamente necesaria.
4. Mecanismo de Visualización: Propuesta e implementación de una herramienta que visualiza la evidencia sobre el Árbol de Sintaxis Abstracta (AST) de la fórmula en cada estado, utilizando codificación de colores (verde/rojo/gris) y distinción entre estados abiertos y cerrados.
5. Demostrador Interactivo: Se presenta una herramienta de software (disponible como artefacto) que permite a los usuarios seleccionar un estado y una subfórmula para ver su evidencia mínima o natural, y combinar estas vistas.

4. Resultados Principales

• Teoremas de Suficiencia y Necesidad: Se demuestra que las condiciones sintácticas propuestas son suficientes para cualquier modelo consistente y necesarias para fórmulas cuyos hijos no están "restringidos" (unconstrained).
• Existencia de Evidencia Combinada: Se prueba que para cualquier modelo sonoro y fórmula CTL, existe una "evidencia combinada" que resume la verificación para todos los estados en un solo modelo, donde la evidencia para un estado específico es simplemente la parte alcanzable de ese modelo combinado.
• Validación Práctica: A través del ejemplo de un juego de tablero, se ilustra cómo la herramienta genera contraejemplos visuales claros (ej. mostrando por qué no se puede ganar sin tirar un 1) y cómo la "evidencia natural" hace que la estructura del contraejemplo sea más fácil de entender que la evidencia puramente mínima.

5. Significado e Impacto

• Puente entre Teoría y Práctica: El trabajo cierra la brecha entre la complejidad teórica de la verificación CTL y la necesidad práctica de los ingenieros de entender por qué un sistema falla o funciona.
• Superación de la Limitación de LTL: Proporciona una alternativa viable a la intuición lineal de LTL para lógicas ramificadas, permitiendo que los contraejemplos en CTL sean tan digeribles como las trazas en LTL.
• Herramienta de Depuración: Al ofrecer visualizaciones interactivas y combinadas, facilita la depuración de especificaciones y modelos complejos, reduciendo el tiempo de análisis humano.
• Fundamento para Futuras Extensiones: La introducción de estados cerrados y la relación con supermodelos abre la puerta a investigar extensiones a lógicas más potentes (como CTL* o $\mu$-cálculo) y a la integración con relaciones de simulación.

En resumen, este artículo transforma la verificación de modelos CTL de un proceso de "caja negra" (verdadero/falso) a un proceso transparente y visual, donde la estructura de la evidencia (testigos y contraejemplos) se presenta de la forma más simple y comprensible posible para el usuario humano.