Module: ppl/w3ppl Branch: master Commit: 4373e638d968910146d9e9c90d4ba34ecbe95e2c URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/w3ppl.git;a=commit;h=4373e638d96...

Author: Roberto Bagnara bagnara@cs.unipr.it Date: Sat Apr 11 10:42:30 2009 +0200

Added BagnaraHZ09TRa.

---

htdocs/Documentation/BagnaraHZ09TRa.pdf | Bin 0 -> 311884 bytes htdocs/Documentation/ppl.bib | 34 +++++++++++++++++++++++++++++++ 2 files changed, 34 insertions(+), 0 deletions(-)

diff --git a/htdocs/Documentation/BagnaraHZ09TRa.pdf b/htdocs/Documentation/BagnaraHZ09TRa.pdf new file mode 100644 index 0000000..d4740b9 Binary files /dev/null and b/htdocs/Documentation/BagnaraHZ09TRa.pdf differ diff --git a/htdocs/Documentation/ppl.bib b/htdocs/Documentation/ppl.bib index 2784df5..d85441d 100644 --- a/htdocs/Documentation/ppl.bib +++ b/htdocs/Documentation/ppl.bib @@ -931,6 +931,40 @@ domains with floating point numbers are also discussed.", }

+@Misc{BagnaraHZ09TRa, + Author = "R. Bagnara and P. M. Hill and E. Zaffanella", + Title = "Exact Join Detection for Convex Polyhedra + and Other Numerical Abstractions", + Howpublished = "Report {\tt arXiv:cs.CG/0904.1783}", + Year = 2009, + Abstract = "Deciding whether the union of two convex polyhedra is a + convex polyhedron is a basic problem in polyhedral + computation having important applications in the field + of constrained control and in the synthesis, analysis, + verification and optimization of hardware and software + systems. In these application fields, though, general + convex polyhedra are only one among many so-called + \emph{numerical abstractions}: these 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/BagnaraHZ09TRa.pdf" +} + @InProceedings{BalasundaramK89, Author = "V. Balasundaram and K. Kennedy", Title = "A Technique for Summarizing Data Access