Verificación de lógicas modales dinámicas en Coq

Abstract

Los lenguajes modales son lenguajes adecuados para describir propiedades de grafos dirigidos con nodos etiquetados. Estas estructuras aparecen en una gran variedad de problemas de diversas áreas del conocimiento. Como consecuencia de esto, existe una gran variedad de lógicas modales. En la práctica cada vez que se define una nueva lógica modal, muchos teoremas deben ser demostrados y revisados nuevamente para esta nueva lógica. Este proceso, además de resultar tedioso, es propenso a errores. Afortunadamente, la tarea de realizar demostraciones complejas ha comenzado cada vez más a ser asistida por herramientas computacionales. En este trabajo, formalizamos y verificamos en el asistente de demostraciones Coq un teorema de invarianza bajo bisimulación de ciertas lógicas modales con operadores dinámicos capaces de modificar la relación de accesibilidad.

Modal languages are adequate languages to describe properties of labelled directed graphs. These structures appear in a wide variety of problems from different areas of knowledge. As a consequence, there exist a great number of modal logics. In practice, every time a new modal logic is defined, many theorems must be proved and peer-reviewed again for this new logic. This process, besides being tedious, is error-prone. Fortunately, the task of writing complex proofs has increasingly begun to be assisted by computational tools. In this work, we formalize and verify an invariance under bisimulation result in the proof assistant Coq for a particular family of dynamic modal logics that change the accessibility relation of a model.