cs@parma

Home

People

Projects

Publications

Seminars

Software

Links

Possibly Not Closed Convex Polyhedra and the Parma Polyhedra Library (TR)

Roberto Bagnara, Elisa Ricci, Enea Zaffanella, and Patricia M. Hill

Abstract

The domain of convex polyhedra is employed in several systems for the analysis and verification of hardware and software components. Current applications span imperative, functional and logic languages, synchronous languages and synchronization protocols, real-time and hybrid systems. Since the seminal work of P. Cousot and N. Halbwachs, convex polyhedra have thus played an important role in the formal methods community and several critical tasks rely on their software implementations. Despite this, existing libraries for the manipulation of convex polyhedra are still research prototypes and suffer from limitations that make their usage problematic, especially in critical applications. These limitations concern inaccuracies in the documentation of the underlying theory, code and interfaces; numeric overflow and underflow; use of not fully dynamic data-structures and poor mechanisms for error handling and recovery. In addition, there is inadequate support for polyhedra that are not necessarily closed (NNC), i.e., polyhedra that are described by systems of constraints where strict inequalities are allowed to occur. This paper presents the Parma Polyhedra Library, a new, robust and complete implementation of NNC convex polyhedra, concentrating on the distinctive features of the library and on the novel theoretical underpinnings.


Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, and BibTeX entry.


Errata

The conjecture (mis-named claim) on pages 13-14 is false. Here is a short note that provides counter-examples to both the statements in the conjecture. Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, and BibTeX entry.

[Page last updated on July 02, 2002, 21:33:16.]

Page maintained by
Enea Zaffanella

Home | People | Projects | Publications | Seminars | Software | Links