Nonmonotonic logic programming (NLP) refers to the class of programming frameworks that are based on some nonmonotonic language constructs. These include default negation, disjunction, choice operators, weight operators, etc. Different semantics have been studied for NLP.
The stable model semantics for NLP is particularly interesting as it provides an alternative, potentially very promising, paradigm for constraint programming. In this setting, a clause
a :- b1, ..., bk, not c1, ... not cj
is interpreted as a constraint: a should be in a solution if b's are in it and c's are not. In addition, under the stable model semantics one can express the denials like
:- b1,...,bk, not c1,..., not cn
which says that any set that contains b's but not c's cannot be a solution.
Example: K-colorability
Given facts about vertex(v), arc(v,u), and available colors col(c), we want to find an assignment of colors to vertices of a graph such that vertices connected with an arc do not have the same color. The following program solves the problem: each stable model of the program is a solution to K-colorability. The program, along with facts about a graph and available colors, can be run in systems such as Smodels or DLV -- a stable model corresponds to a solution to K-colorability.
color(V,C) :- vertex(V), col(C), not otherColor(V,C).
otherColor(V,C) :- vertex(V), col(C), col(D), C =/= D, color(V,D).
:- arc(V,U), col(C), color(V,C), color(U,C).
The first two rules generate candidate solutions using an auxiliary predicate otherColor(V,C), while the constraint eliminates illegal ones.
Logic programming with negation can express all problems in NP, and is arguably more expressive than some other frameworks such as SAT and CSP. Recent advances in implementation techniques have made it possible to compete with SAT and CSP solvers, and some planning procedures.
A disjunctive clause
a1 or ... or ak :- b1, ..., bk, not c1, ... not cj
can be interpreted in a similar way. Disjunctive logic programming generally raises the expressive power to the second level of the polynomial hierarchy. It can be used to express computational problems that cannot be expressed in some other frameworks.
Compared to traditional monotonic constraint languages, it seems that it is the groundedness and minimality of stable models that enables more concise specifications of constraints in some situations. In a single instance, it is argued that the most concise encodings of the existence of a hamiltonian cycle problem as the problem of the existence of a stable model of a logic program are asymptotically more concise than similar encodings as the problem of the existence of a satisfying valuation of a CNF formula.
What appears to be more promising is that the best implementations of logic programming systems seem to be able to compete with the best special systems particularly designed for narrower domains of problems. For example, Niemela reported that some research groups had started using the Smodels system for planning and found that Smodels performed as well as, sometimes better than, some of the special planning algorithms.
Despite these promising developments, important questions remain to be answered. First, it is important to have a more precise comparison between the techniques used in logic programming systems and those in other AI systems. Such a comparison may help us understand the nature of the NLP based constraint solvers.
Considering the recent progress in algorithms for satisfiability testing, and the fact that all decision problems in NP can be reduced polynomially to satisfiability testing, the question ``why NLP'' naturally arises. This is a challenging open problem. It is commonly believed that groundedness and minimality of stable models contribute to some of the unique features of NLP. Another important factor is that, as a general knowledge representation language, NLP enables flexible methodologies to represent constraints. For example, some lookahead mechanism can be coded into the representing (logic) program of a constraint problem.
Current implementations to generate stable models deal with ground programs. A function-free, nonground program is first instantiated to a ground program, and its stable models are then computed. This may sometimes generate a large ground program. The question is open as whether a goal directed query answering procedure directly over nonground programs is possible. One possible approach is to compile programs under stable semantics to programs under partial stable semantics for which a goal directed query answering procedure exists. The theoretical basis for this possibility is that brave reasoning (show that a goal is true in anyone of the intended models) for both fall into the same complexity class so in theory there exists a polynomial reduction from one to the other.