[PPL-devel] Complexity of remove_dimensions

[Roberto Bagnara]

Mario Mendez wrote:
> Hi again,
> 
> I'm wondering what is the complexity (worst case, O(f(x,y)) for the 
> 'remove_dimensions' method offered in the library. I checked the source 
> code but it is kind of difficult to me to figure out the exact function.

Dear Mario,

the worst case, time and space complexity of 'remove_space_dimensions'
(please note the 'space' between 'remove' and 'dimensions') is
exponential in the number of space dimensions of the original
polyhedron.  This answer is not very precise, but is good enough
for most practical purposes.  Please let us know if this is good
enough for your purposes.

> Another question: is there any "standard" algorithm to project a system 
> of linear (in)equations on certain dimensions, in the same way 
> 'remove_dimensions' is doing? If so, what is its name?

Ehm, Mario, where is the camera?  Come on, I just know this has
got to be "Candid camera"!   :-D

This is the third time you ask the same question:

   http://www.cs.unipr.it/pipermail/ppl-devel/2005-July/006205.html
   http://www.cs.unipr.it/pipermail/ppl-devel/2005-July/006263.html

Its name (please write it down _now_ :-) is 'map_space_dimensions'.
If you think 'map_space_dimension' is not what you need, if by
`"standard" algorithm' you meant something different, then (quoting
what I wrote in 
http://www.cs.unipr.it/pipermail/ppl-devel/2005-July/006205.html):
"Please, come back to us with a clearer explanation of what you have,
what you do and what you want, so that we can see what is your best
option."

> Thank you!

It's a pleasure Mario.  You can also help us make the PPL better.
For instance, Manuel Hermenegildo mentioned that someone (perhaps
you?) found inaccuracies in our installation instructions for the
Ciao Prolog interface of the PPL.  Is this correct?  If so, could
you let us know so that we can improve the documentation?
Did you have to patch the code too?  If so, can you let us have
the details?

Another thing we would like to know are the versions of Ciao Prolog
and of the PPL you are using and whether you have experienced the
problem described in

   http://www.cs.unipr.it/pipermail/ppl-devel/2004-October/004971.html

If so, do you know if a cure is available?
Many thanks in advance,

     Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it