Verifying Hierarchical Ptolemy II discrete-event models using Real-Time Maude

EL 29 de Octubre se publicó un nuevo artículo de vrificación: Verifying Hierarchical Ptolemy II discrete-event models using Real-Time Maude, Science of Computer Programming en la revista Science of Computer Programming.

Los autores del artículo son Kyungmin Bae (de la University de Illinois en Urbana-Champaign), Peter Csaba Olveczky (de la Universidad de Oslo), Thomas Huining Feng, Edward A. Lee y Stavros Tripakis (los tres últimos, de la Universidad de California en Berkeley).

El resumen del artículo es

This paper defines a real-time rewriting logic semantics for a significant subset of Ptolemy II discrete-event models. This is a challenging task, since such models combine a synchronous fixed-point semantics with hierarchical structure, explicit time, and a rich expression language. The code generation features of Ptolemy II have been leveraged to automatically synthesize a Real-Time Maude verification model from a Ptolemy II design model, and to integrate Real-Time Maude verification of the synthesized model into Ptolemy II. This enables a model-engineering process that combines the convenience of Ptolemy II DE modeling and simulation with formal verification in Real-Time Maude. We illustrate such formal verification of Ptolemy II models with three case studies.

Una versión previa del artículo, de libre acceso, es Verifying Hierarchical Ptolemy II discrete-event models using Real-Time Maude.

Extending Clause Learning of SAT Solvers with Boolean Gröbner Bases

Se ha publicado recientemente el artículo Extending Clause Learning of SAT Solvers with Boolean Gröbner Bases.

En el artículo se presenta una forma de combinar sistemas SAT (basados en el algoritmo DPLL) y bases de Gröbner de forma que cuando se encuentran conflictos, el aprendizaje de las nuevas cláusulas se realice mediante bases de Gröbner en lugar de hacerlo por resolución.

Para experimentar la propuesta, han creado el sistema MiniSat+GB en el que integran el sistema MiniSat con la librería para el cálculo de bases de Gröbner del sistema de cálculo simbólico Reduce.

En los resultados de los experimentos se observa cómo MiniSat+GB supera en eficiencia a MiniSat en los casos en los que se requiere más tiempo de cómputo.

Los autores del artículo son Christoph Zengler y Wolfgang Küchlin que son miembros del Grupo de cálculo simbólico de la Universidad de Tubinga (Tübingen en alemán), Alemania.

El artículo se ha publicado en el LNCS 6244: Computer Algebra in Scientific Computing. (12th International Workshop, CASC 2010)

Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks

Se ha publicado un nuevo artículo de formalización: Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks

Los autores del artículo son Freek Verbeek y Julien Schmaltz de la Universiad de Radboud en Nimega (en neerlandés: Nijmegen), Paises Bajos.

El artículo se publicó ayer (18 de Septiembre de 2010) en el Journal of Automated Reasoning.

Una versión preliminar del artículo puede leerse aquí y el código ACL2 correspondiente puede obtenerse aquí

El artículo es una demostración en ACL2 de una condición necesaria y suficiente para enrutamiento sin estancamiento introducida por William J. Dally y Charles L. Seitz en su artículo Deadlock Free Message Routing in Multiprocessor Interconnection Networks de 1987.
Read More “Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks”

Anuncio: Trace-based verification of imperative programs with I/O

Gregory Malecha, Greg Morrisett y Ryan Wisnesky han publicado el artículo Trace-based verification of imperative programs with I/O en el Journal of Symbolic Computation. Una versión del artículo puede leerse aquí.

El resumen del artículo es

In this paper we demonstrate how to prove the correctness of systems implemented using low-level imperative features like pointers, files, and socket I/O with respect to high level I/O protocol descriptions by using the Coq proof assistant. We present a web-based course gradebook application developed with Ynot, a Coq library for verified imperative programming. We add a dialog-based I/O system to Ynot, and we extend Ynot’s underlying Hoare logic with event traces to reason about I/O and protocol behavior. Expressive abstractions allow the modular verification of both high level specifications like privacy guarantees and low level properties like data structure pointer invariants.

Los autores son miembros del Grupo de Lenguajes de Programación de la Universidad de Harvard.

Este artículo está relacionado con el proyecto SAFE (Semantically Aware Foundation Environment) comentado en una entrada anterior.