Stable model semantics and an alternative logic programming paradigm Victor W. Marek and Miroslav Truszczynski Abstract: This paper reexamines the role of stable model semantics in logic programming and contrasts it with the least Herbrand model approach to Horn programs. We demonstrate that stable model semantics naturally lead to a logic programming system that offers an alternative to traditional logic programming styles. The proposed approach interprets program clauses as constraints, leading to a family of stable models that encode solutions to constraint satisfaction problems. The approach restricts the syntax of logic programs by eliminating function symbols, resulting in a system well-suited for problems in the class NP. Recent progress in implementing algorithms to compute stable models of propositional logic programs makes this approach viable. Introduction: Stable model semantics, introduced in the late 80s, was initially met with skepticism by the logic programming community. While it properly handles negation, it does not fit into the standard paradigm of logic programming. Stable model semantics assigns a family of models to a program, unlike the single intended model of traditional logic programming. This approach leads to a computational system that is declarative, retains the separation of logic from control, and has a well-defined domain of applications. This system is referred to as stable logic programming (SLP). Key elements of stable model semantics include restricting the syntax by disallowing function symbols, viewing programs as specifying a collection of models rather than a single model, and interpreting programs as sets of constraints. SLP is particularly well-suited for problems where solutions are subsets of some universe, as each solution can be modeled by a different stable model. Many combinatorial and constraint satisfaction problems fall into this category. SLP follows the basic logic programming tenet of "uniform control," but uses backtracking search for stable models instead of SLD-resolution. While Horn logic programming is well-suited for Turing computability and recursively enumerable sets, SLP is related to a much narrower class of problems. All decision problems in NP can be solved within the SLP paradigm, and many search problems whose decision versions are in NP can also be solved with SLP programs. SLP is related to the class of problems solvable by default logic, a formalism extending SLP. Recent developments in implementing algorithms to compute stable models have made these alternative logic programming systems viable computational tools. The paper discusses the expressive power of SLP, showing that it is attuned to the class NP. It also discusses the limitations of recursion in SLP and shows that SLP programs should be interpreted as descriptions of sets of constraints. The methodology of programming with SLP is different from that of ordinary logic programming. The paper also discusses the issue of uniform control in SLP and concludes that SLP can evolve into a useful computational tool. It presents several examples of SLP programs that solve various problems, including the hamiltonian cycle problem and the satisfiability problem for propositional CNF formulas.Stable model semantics and an alternative logic programming paradigm Victor W. Marek and Miroslav Truszczynski Abstract: This paper reexamines the role of stable model semantics in logic programming and contrasts it with the least Herbrand model approach to Horn programs. We demonstrate that stable model semantics naturally lead to a logic programming system that offers an alternative to traditional logic programming styles. The proposed approach interprets program clauses as constraints, leading to a family of stable models that encode solutions to constraint satisfaction problems. The approach restricts the syntax of logic programs by eliminating function symbols, resulting in a system well-suited for problems in the class NP. Recent progress in implementing algorithms to compute stable models of propositional logic programs makes this approach viable. Introduction: Stable model semantics, introduced in the late 80s, was initially met with skepticism by the logic programming community. While it properly handles negation, it does not fit into the standard paradigm of logic programming. Stable model semantics assigns a family of models to a program, unlike the single intended model of traditional logic programming. This approach leads to a computational system that is declarative, retains the separation of logic from control, and has a well-defined domain of applications. This system is referred to as stable logic programming (SLP). Key elements of stable model semantics include restricting the syntax by disallowing function symbols, viewing programs as specifying a collection of models rather than a single model, and interpreting programs as sets of constraints. SLP is particularly well-suited for problems where solutions are subsets of some universe, as each solution can be modeled by a different stable model. Many combinatorial and constraint satisfaction problems fall into this category. SLP follows the basic logic programming tenet of "uniform control," but uses backtracking search for stable models instead of SLD-resolution. While Horn logic programming is well-suited for Turing computability and recursively enumerable sets, SLP is related to a much narrower class of problems. All decision problems in NP can be solved within the SLP paradigm, and many search problems whose decision versions are in NP can also be solved with SLP programs. SLP is related to the class of problems solvable by default logic, a formalism extending SLP. Recent developments in implementing algorithms to compute stable models have made these alternative logic programming systems viable computational tools. The paper discusses the expressive power of SLP, showing that it is attuned to the class NP. It also discusses the limitations of recursion in SLP and shows that SLP programs should be interpreted as descriptions of sets of constraints. The methodology of programming with SLP is different from that of ordinary logic programming. The paper also discusses the issue of uniform control in SLP and concludes that SLP can evolve into a useful computational tool. It presents several examples of SLP programs that solve various problems, including the hamiltonian cycle problem and the satisfiability problem for propositional CNF formulas.