[PPL-devel] Feasibility of Octagons in PPL

[Roberto Bagnara]

On 06/17/11 18:03, Ramakrishna Upadrasta wrote:
> Hello All,

Hi Ramakrishna.

> I would like to know if there is any feasibility test developed
> specifically of octagons in PPL. I am looking for a solution to the
> following problem: given a set of octagonal constraints, determine if
> the system is empty or not.

http://www.cs.unipr.it/ppl/Documentation/user/ppl-user-0.11.2-html/classParma__Polyhedra__Library_1_1Octagonal__Shape.html#a353fe86259fbb2dd09d451e9dd468676

> If so, what are its details (method followed, complexity etc.)?

It is basically a transitive closure, cubic in the worst case in the
number of dimensions of the octagonal shape.
Cheers,

    Roberto

-- 
Prof. Roberto Bagnara
Applied Formal Methods Laboratory
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it