We are very happy to announce the availability of PPL 0.6, the latest release of the Parma Polyhedra Library.

More than a year has passed since the previous release. During this period we have been doing a considerable amount of research and development work and this release, which is the first of a series of official versions that we hope to publish in the very near future, incorporates some of this work.

The main focus of this release is on complete support for powersets of polyhedra. This includes the customizable framework for the definition of widening operators we have proposed at this year's VMCAI conference. Then there is support for summary dimensions as proposed by Denis Gopan and colleagues in their TACAS 2004 paper. We have started adding demo programs to the library. One of them, `ppl_lcdd', is actually useful and is competitive with similar programs available out there. Many other improvements have been performed: documentation, performance, portability and the configuration machinery have all been improved. A handful of bugfixes complete the picture: see below for more details.

For more information, visit the PPL web site at

http://www.cs.unipr.it/ppl/

The PPL development team:

Roberto Bagnara bagnara@cs.unipr.it Patricia M. Hill hill@comp.leeds.ac.uk Enea Zaffanella zaffanella@cs.unipr.it

New and Changed Features ========================

o New templatic classes Determinate, PowerSet, and Polyhedra_PowerSet. The first two classes realize, in a completely generic way, the determinate and powerset constructions described by Roberto Bagnara in his 1998, Science of Computer Programming paper. The third class is a specialization of the powerset construction on polyhedra. The powerset construction comes with the generic widening technique proposed by Roberto Bagnara, Patricia Hill and Enea Zaffanella in their VMCAI 2004 paper. Actually, the Polyhedra_PowerSet class provides the first genuine, non-trivial widening ever proposed (let alone made available) on a domain of sets of convex polyhedra.

o New methods

void Polyhedron::expand_dimension(Variable, dimension_type) and void Polyhedron::fold_dimensions(const Variables_Set&, Variable)

allow the easy realization of summary dimensions as proposed by Denis Gopan and colleagues in their TACAS 2004 paper.

o A new `demos' directory has been added. In the `ppl_lcdd' subdirectory, this contains a sort of clone of the cddlib test program `lcdd', written using the PPL's C++ interface, together with several example polyhedra in the formats that the program can handle. The `ppl_lpsol' subdirectory contains another demo program that solves linear programming problems by vertex/point enumeration. This is written using the PPL's C interface and comes with several example problems in the Mathematical Programming System (MPS) format. In order to read MPS files, `ppl_lpsol' uses the GNU Linear Programming Kit (GLPK); thus `ppl_lpsol' is only compiled if a suitable version of GLPK is available.

o New macro PPL_VERSION expands to the version string of the library.

o New file README.configure provides additional information about the configuration and compilation of the library.

o The documentation has been improved in various ways.

o The documentation for users, in PostScript, PDF and HTML formats, is now installed in a standard place by `make install'.

o The variable `abandon_exponential_computations' has been renamed `abandon_expensive_computations'.

o The methods

void Polyhedron::add_constraints(ConSys& cs), void Polyhedron::add_generators(GenSys& gs), bool Polyhedron::add_constraints_and_minimize(ConSys& cs), and bool Polyhedron::add_generators_and_minimize(GenSys& gs)

have been renamed

void Polyhedron::add_recycled_constraints(ConSys& cs), void Polyhedron::add_recycled_generators(GenSys& gs), bool Polyhedron::add_recycled_constraints_and_minimize(ConSys& cs), and bool Polyhedron::add_recycled_generators_and_minimize(GenSys& gs),

respectively. At the same time, the methods

void Polyhedron::add_constraints(const ConSys& cs), void Polyhedron::add_generators(const GenSys& gs), bool Polyhedron::add_constraints_and_minimize(const ConSys& cs), and bool Polyhedron::add_generators_and_minimize(const GenSys& gs)

have been added. Corresponding changes have been made to the C and Prolog interfaces.

o New methods Polyhedron::maximize() and Polyhedron::minimize() for maximizing and minimizing a linear expression subject to the polyhedron.

o New output operator in namespace IO_Operators: std::ostream& operator<<(std::ostream&, const LinExpression&).

o The method Polyhedron::map_dimensions(const PartialFunction& pfunc) has been significantly optimized for the case when `pfunc' is a permutation. A simple "renaming" of the dimensions is now extremely cheap.

o The function Parma_Polyhedra_Library::max_space_dimension() has been given a new semantics and destiny: it returns the maximum space dimension that _all_ the abstractions provided by the library can handle. Each individual abstraction provides its versions of this function. Thus, e.g., NNC_Polyhedron::max_space_dimension() gives the maximum space dimensions an NNC_Polyhedron can handle.

o The type of output functions for the class Variable, `Variable::Output_Function_Type', has been renamed `Variable::output_function_type' and is now defined as void output_function_type(std::ostream& s, const Variable& v). In other words, `v' is now passed by const reference and not by value.

o Thanks to Bruno Haible, it is now possible to use versions of the GMP library installed into nonstandard places. The new configure options --with-libgmp-prefix[=DIR] and --with-libgmpxx-prefix[=DIR] substitute the old (and not really working) options --with-gmp-includes=DIR and --with-gmp-dir=DIR.

Bugfixes ========

o Fixed a bug in the C interface function ppl_Polyhedron_map_dimensions() whereby a wrong result was computed.

o Fixed a bug in Polyhedron::poly_difference_assign(const Polyhedron&) whereby a wrong result was computed.

o Fixed a bug in the Prolog interface predicate ppl_Polyhedron_get_bounding_box/3 whereby a wrong result was sometimes computed in the case of an empty polyhedron.

o Fixed a bug in the Prolog interface predicate ppl_new_Polyhedron_from_bounding_box/3 whereby the predicate was failing when given an empty bounding box.