18 Sep 1998 | Victor W. Marek, Mirosław Truszczyński
This paper re-examines the role of stable model semantics in logic programming and contrasts it with the least Herbrand model approach to Horn programs. The authors propose a new perspective on stable model semantics, which is based on interpreting program clauses as constraints. This approach leads to a logic programming system that offers an interesting alternative to traditional logic programming styles, such as Horn logic programming, stratified logic programming, and logic programming with well-founded semantics. The proposed system, called *stable logic programming* (SLP), restricts the syntax by disallowing function symbols, making it well-suited for problems in the NP class. SLP programs specify a family of stable models, each of which encodes solutions to the constraint satisfaction problem described by the program. The authors argue that SLP is well-attuned to problems in NP, has a well-defined domain of applications, and an emerging methodology of programming. They also discuss the limitations of recursion in SLP and the need for a different approach to programming, where clauses act as constraints rather than recursive definitions. The paper includes examples of how SLP can be used to solve combinatorial and constraint satisfaction problems, and concludes with a discussion of uniform control in SLP.This paper re-examines the role of stable model semantics in logic programming and contrasts it with the least Herbrand model approach to Horn programs. The authors propose a new perspective on stable model semantics, which is based on interpreting program clauses as constraints. This approach leads to a logic programming system that offers an interesting alternative to traditional logic programming styles, such as Horn logic programming, stratified logic programming, and logic programming with well-founded semantics. The proposed system, called *stable logic programming* (SLP), restricts the syntax by disallowing function symbols, making it well-suited for problems in the NP class. SLP programs specify a family of stable models, each of which encodes solutions to the constraint satisfaction problem described by the program. The authors argue that SLP is well-attuned to problems in NP, has a well-defined domain of applications, and an emerging methodology of programming. They also discuss the limitations of recursion in SLP and the need for a different approach to programming, where clauses act as constraints rather than recursive definitions. The paper includes examples of how SLP can be used to solve combinatorial and constraint satisfaction problems, and concludes with a discussion of uniform control in SLP.