School of Computing

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 kbytes

Bibtex 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)},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014