A theoretical framework for consistency techniques in logic programming

Abstract

While being a powerful paradigm for solving Constraint Satisfaction Problems (CSPs), Consistency Techniques (CTs) have never been taken into account during the design of declarative programming languages. This paper defines a theoretical framework for using CTs inside logic programming. Three inference rules are introduced and their formal properties are investigated. Also, computation rules are defined which are worth considering wrt the inference rules. As practical results, the programmer can write generate & test programs while the interpreter/compiler will use CTs for solving them (e.g forward checking or arc consistency). This makes logic programming not only a good language for stating CSPs but also an efficient tool for solving them as confirmed by our first experiences.