Certificación computacional del conocimiento matemático

Esta entrada está dedicada a los antecentes de la certificación computacional del conocimiento matemático en estilo declarativo.

Por lo que respecta a la verificación declarativa, sus raices se encuentran en el trabajo realizado en el proyecto Mizar. El proyecto Mizar comenzó en el 1973 como un intento de reconstruir la matemática en un entorno computacionalmente certificable. Los teoremas demostrados dentro del proyecto Mizar se encuentran fundamentalmente en la Mizar Mathematical Library y en la revista Formalized Mathematics que se publica desde el año 1990. El sistema Mizar no es automático sino que es sólo un verificador. Por contra, los sistemas de demostración no disponían de modos de demostración declararativa hasta que M. Wenzel creó Isar (Intelligible semi-automated reasoning). Isar está construido sobre el sistema Isabelle. Isabelle es un asistente de prueba genérico desarrollado por L. Paulson (en la Universidad de Cambridge) y T. Nipkow (en la Universidad Politécnica de Munich). Las teorías formalizadas en Isabelle/Isar se encuentran fundamentalmente en la biblioteca de Isabelle2009-1, en la revista The Archive of Formal Proofs y en la IsarMathLib (A library of formalized mathematics for Isabelle/ZF theorem proving environment).

Por lo que respecta a la certificación computacional del conocimiento
matemático los antecedentes pueden situarse en el 1993 con la publicación del manifiesto del proyecto QED impulsado por Bob Boyer y la revisión del proyecto QED en 2007 por F. Wiedijk. Actualmente se han demostrado muchos teoremas matemáticos importantes, como puede comprobarse en Formalizing 100 Theorems, en la NASA Langley PVS Libraries y en The Coq Users’ Contributions. Entre los teoremas formalmente certificados podemos citar el teorema de de la distribución de los números primos, el teorema de los cuatro colores y el teorema de la curva de Jordan. Nuestro grupo posee experiencia en la certificación de teoremas matemáticos habiendo certificado en ACL2 y PVS, entre otros, el lema de Newman, el teorema de Knuth-Bendix, el teorema de corrección del algoritmo de Buchberger, el teorema de Bezem de completitud de la resolución proposicional y el teorema de completitud de la resolución SLD.

Razonamiento formalizado en análisis numérico

Hoy se ha publicado en arXiv el artículo Formal Proof of a Wave Equation Resolution Scheme: the Method Error escrito por Sylvie Boldo (INRIA Saclay – Ile de France, LRI), Francois Clement (INRIA Rocquencourt), Jean-Christophe Filliâtre (INRIA Saclay – Ile de France, LRI), Micaela Mayero (LIPN, INRIA Rhône-Alpes / LIP Laboratoire de l’Informatique du Parallélisme), Guillaume Melquiond (INRIA Saclay – Ile de France, LRI) y Pierre Weis (INRIA Rocquencourt).

En este trabajo se presenta una formalización en Coq de una parte del conocimiento matemático más usado en las ingeniería: las ecuaciones diferenciales. Curiosamente las ecuaciones diferenciales apenas se han tratado dentro del razonamiento formalizado.

Read More “Razonamiento formalizado en análisis numérico”

SBMF 2010: 13th Brazilian Symposium on Formal Methods

El SBMF 2010: 13th Brazilian Symposium on Formal Methods se celebrará en Natal (Rio Grande do Norte, Brazil) del 8 al 12 de Noviembre.

Entre los temas del congreso relacionados con el trabajo de nuestro grupo están:

  1. Especificación y modelización.
  2. Técnicas de abstracción, modularización y refinamiento.
  3. Demostración automática de teoremas.
  4. Certificación de software.
  5. Enseñanza de, y con, métodos formales.
  6. Desarrollo de metodogías basadas en métodos formales.

La fecha de envío de artículos finaliza el 10 de Junio.

PAR-2010: Workshop on Partiality and Recursion in Interactive Theorem Provers

Dentro del marco del ITP’01 se va a celebrar el PAR-2010: Workshop on Partiality and Recursion in Interactive Theorem Provers.

Uno de los temas del congreso es la automatización de las demotraciones de terminación de funciones. Sobre este tema hemos trabajado en nuestro grupo tanto en ACL2 como en PVS.

El congreso se celebrará el 15 de Julio en Edimburgo. El plazo de envío de artículos termina el 19 de marzo.

Reseña – A Formalization of the Knuth–Bendix(–Huet) Critical Pair Theorem

El día 21 se publicó en el Journal of Automated Reasoning el artículo A Formalization of the Knuth–Bendix(–Huet) Critical Pair Theorem/a> escrito por André L. Galdino y Mauricio Ayala Rincón. En el trabajo se presenta una formalización en PVS del teorema de pares críticos. También es pública la teoría PVS con la formalización.

Este trabajo es la continuación de anteriores trabajos de los autores

  1. A Theory for Abstract Reduction Systems in PVS
  2. Verification of Newman’s and Yokouchi Lemmas in PVS
  3. A PVS theory for Term Rewriting Systems

Todos estos trabajos son extensiones de la tesis de André L. Galdino Uma formalização da teoria de reescrita em linguagem de ordem superior dirigida por Mauricio Ayala Rincón. En la tesis se realiza una formalización en PVS de los sistemas de reescritura semejante a la realizada en ACL2 por José Luis Ruiz Reina en su tesis Una teoría computacional acerca de la lógica ecuacional (formalización ACL2 de la lógica ecuacional y demostración automática de sus propiedades).