Roberto Bagnara wrote:
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.
More than enough, thanks
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."
Actually, we are in the second case. I'm asking whether the algorithm used in 'remove_dimensions' has an standard name (in Math literature) so I can google for it to get more information, in the same way the algorithm to solve a system of lin.eq. is called 'Gaussian elimination', for instance.
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?
The only problem I found is that the instructions do not mention the (required)
/sbin/ldconfig
command necessary to update the system in order to 'accept' PPL.
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?
I did not experienced that problem. I'm using PPL 0.7 + SVN Ciao (therefore, no particular release of Ciao).
Many thanks in advance,
Roberto