Module: ppl/w3ppl Branch: master Commit: 2f467f99eb8834996cbe183be0ca3660387b1055 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/w3ppl.git;a=commit;h=2f467f99eb8...
Author: Roberto Bagnara bagnara@cs.unipr.it Date: Tue Sep 29 20:24:01 2009 +0200
Added BagnaraHZ09CGTA.
---
htdocs/Documentation/ppl.bib | 37 +++++++++++++++++++++++++++++++++++++ 1 files changed, 37 insertions(+), 0 deletions(-)
diff --git a/htdocs/Documentation/ppl.bib b/htdocs/Documentation/ppl.bib index 2421342..80ff5e3 100644 --- a/htdocs/Documentation/ppl.bib +++ b/htdocs/Documentation/ppl.bib @@ -869,6 +869,43 @@ URL = "http://www.cs.unipr.it/ppl/Documentation/BagnaraHZ08SCP.pdf" }
+@Article{BagnaraHZ09CGTA, + Author = "R. Bagnara and P. M. Hill and E. Zaffanella", + Title = "Exact Join Detection for Convex Polyhedra + and Other Numerical Abstractions", + Journal = "Computational Geometry: Theory and Applications", + Publisher = "Elsevier", + Year = 2009, + Note = "To appear", + Abstract = "Deciding whether the union of two convex polyhedra is + itself a convex polyhedron is a basic problem in + polyhedral computations; having important applications + in the field of constrained control and in the + synthesis, analysis, verification and optimization of + hardware and software systems. In such application + fields though, general convex polyhedra are just one + among many, so-called, \emph{numerical abstractions}, + which range from restricted families of (not necessarily + closed) convex polyhedra to non-convex geometrical + objects. We thus tackle the problem from an abstract + point of view: for a wide range of numerical + abstractions that can be modeled as bounded + join-semilattices ---that is, partial orders where any + finite set of elements has a least upper bound---, we + show necessary and sufficient conditions for the + equivalence between the lattice-theoretic join and the + set-theoretic union. For the case of closed convex + polyhedra ---which, as far as we know, is the only one + already studied in the literature--- we improve upon the + state-of-the-art by providing a new algorithm with a + better worst-case complexity. The results and + algorithms presented for the other numerical + abstractions are new to this paper. All the algorithms + have been implemented, experimentally validated, and + made available in the Parma Polyhedra Library.", + URL = "http://www.cs.unipr.it/ppl/Documentation/BagnaraHZ09CGTA.pdf" +} + @Article{BagnaraHZ09TCS, Author = "R. Bagnara and P. M. Hill and E. Zaffanella", Title = "Applications of Polyhedral Computations to the Analysis