Dada una especificación, ¿la satisface un programa?
He estado leyendo algunos artículos sobre tipos dependientes y contratos de programación. De la mayoría de lo que he leído, parece que los contratos se comprueban dinámicamente y los tipos dependientes se comprueban estáticamente. Ha habido algunos documentos que me han hecho pensar que es posible...
Estoy aprendiendo métodos formales. Escuché que se usan métodos formales (y generalmente solo se usan) para crear software de misión crítica (como el controlador del reactor nuclear, el controlador de vuelo de la aeronave, el controlador de la sonda espacial). Por eso me interesa aprenderlo: p Sin...
Los esfuerzos de verificación del compilador a menudo se reducen a demostrar que el compilador es completamente abstracto: que conserva y refleja las equivalencias (contextuales). En lugar de proporcionar pruebas de abstracción completas, algunos trabajos de verificación de compiladores recientes...
La pregunta: Supongamos que tengo una especificación de un problema que consiste en axiomas y una meta (es decir, el problema de prueba asociado es si la meta es satisfactoria dados todos los axiomas). Supongamos también que el problema no contiene inconsistencias / contradicciones entre los...
Si está familiarizado con la verificación del programa, es probable que prefiera leer la Pregunta antes que los Antecedentes . Si no está familiarizado con la verificación del programa, es posible que aún pueda responder esta pregunta, pero es probable que prefiera leer el Fondo...
La semántica de un gran subconjunto de OCaml, llamada OCamllight , fue formalizada en HOL por Owens hace varios años. Más recientemente, Kreitz, Hayden y Hickey implementaron una semántica teórica tipo de un subconjunto más pequeño de OCaml en Nuprl . ¿Hay algún desarrollo similar en...
Encontré que los sistemas de transición etiquetados son un buen modelo para mi aplicación, es decir, hay un documento sobre modelos de casos de uso con LTS. La pregunta es, ¿qué se puede probar fácilmente sobre los LTS? Me gustaría reutilizar las soluciones existentes para ver si son útiles para mi...
La lógica monádica de primer orden, también conocida como la clase monádica del problema de decisión, es donde todos los predicados toman un argumento. Se demostró que era decidible por Ackermann, y está NEXPTIME-complete . Sin embargo, problemas como SAT y SMT tienen algoritmos rápidos para...
Quizás la principal fuente de problemas de rendimiento en Haskell es cuando un programa sin darse cuenta acumula una cantidad de profundidad ilimitada, lo que provoca una pérdida de memoria y un desbordamiento potencial de la pila al evaluar. El ejemplo clásico se define sum = foldr (+) 0en...
Como no se dio respuesta, se ha establecido una bandera solicitando que esta pregunta se convierta en una wiki comunitaria. Los comentarios de Aaron Sterling, Sasho Nikolov y Vor se sintetizaron en la siguiente resolución, que está abierta para la discusión de la wiki comunitaria: Resuelto:...
En el clásico artículo PLDI'98 de Necula, "El diseño e implementación de un compilador certificador", el verificador de alto nivel utiliza: VCGen para generar condiciones de verificación (predicados de seguridad) Probador del teorema lógico de primer orden para probar las condiciones Comprobador...
Estoy escribiendo un modelo de juguete , y estoy en el punto en que es hora de implementar la traducción de autómatas LTL a Buchi. Por una variedad de razones obvias, deseo que el algoritmo sea simple :) por ejemplo, quiero que el código permanezca extremadamente claro y conciso durante el mayor...
Estoy tratando de desarrollar algunas nociones de un cálculo de diferencia entre una máquina ideal de Turing ideal concebida por un desarrollador (por ejemplo, lo que sea que pretenda un desarrollador de software), llámelo y las máquinas que representan el software que realmente se diseñó y...
Estoy buscando fuentes sobre la noción formal de programas. Esto parece estar estrechamente relacionado con la correspondencia de Curry-Howard, pero también podría rastrearse hasta Universal Turing Machines y su capacidad para leer la descripción y la entrada de cualquier TM. Al leer sobre la...
Estoy buscando el documento original donde Hoare (o alguien más, supongo) discute la terminación (corrección total). O cualquier otro trabajo inicial sobre la terminación de la lógica "vainilla" de Hoare (supongo que con eso me refiero a un HL para un lenguaje de juguete tipo C). He echado un...