© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Specialising Finite Domain Programs using Polyhedra
J.M. Howe and A. King
In A. Bossi, editor, Logic Programming, Synthesis and Transformation (Selected Papers), volume 1817 of Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, March 2000 Copyright Springer-Verlag, see http://www.springer.de./comp/lncs/index.html.Abstract
A procedure is described for tightening domain constraints of finite domain logic programs by applying a static analysis based on convex polyhedra. Individual finite domain constraints are over-approximated by polyhedra to describe the solution space over (unknown variable n)$ integer variables as an (unknown variable n)$ dimensional polyhedron. This polyhedron is then approximated, using projection, as an (unknown variable n)$ dimensional bounding box that can be used to specialise and improve the domain constraints. The analysis can be implemented straightforwardly and an empirical evaluation of the specialisation technique is given.
Download publication 64 kbytesBibtex Record
@inproceedings{1004, author = {Howe, J.M. and King, A.}, title = {{Specialising Finite Domain Programs using Polyhedra}}, month = {March}, year = {2000}, pages = {182-196}, keywords = {determinacy analysis, Craig interpolants}, note = {Copyright Springer-Verlag, see http://www.springer.de./comp/lncs/index.html}, doi = {}, url = {http://www.cs.kent.ac.uk/pubs/2000/1004}, editor = {Bossi, A.}, publication_type = {inproceedings}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, submission_id = {11182_952013211}, volume = {1817}, booktitle = {Logic Programming, Synthesis and Transformation (Selected Papers)}, }