Computer Science – Data Structures and Algorithms
Scientific paper
2007-05-31
Computer Science
Data Structures and Algorithms
15 pages, 2 figures
Scientific paper
Integer octagonal constraints (a.k.a. ``Unit Two Variables Per Inequality'' or ``UTVPI integer constraints'') constitute an interesting class of constraints for the representation and solution of integer problems in the fields of constraint programming and formal analysis and verification of software and hardware systems, since they couple algorithms having polynomial complexity with a relatively good expressive power. The main algorithms required for the manipulation of such constraints are the satisfiability check and the computation of the inferential closure of a set of constraints. The latter is called `tight' closure to mark the difference with the (incomplete) closure algorithm that does not exploit the integrality of the variables. In this paper we present and fully justify an O(n^3) algorithm to compute the tight closure of a set of UTVPI integer constraints.
Bagnara Roberto
Hill Patricia M.
Zaffanella Enea
No associations
LandOfFree
An Improved Tight Closure Algorithm for Integer Octagonal Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Improved Tight Closure Algorithm for Integer Octagonal Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Improved Tight Closure Algorithm for Integer Octagonal Constraints will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-289037