Skip to main content
Article
What is Answer Set Programming to Propositional Satisfiability
Constraints (2016)
  • Yuliya Lierler, University of Nebraska at Omaha
Abstract
Propositional satisfiability  (or satisfiability) and answer set programming are two closely related subareas of Artificial Intelligence that are used to model and solve difficult combinatorial search problems. Satisfiability solvers and answer set solvers  are the software systems that  find  satisfying interpretations and answer sets for given propositional formulas and logic programs, respectively. These systems are closely related in their common design patterns. In satisfiability, a propositional formula is used to encode problem specifications in a way that its satisfying interpretations correspond to the solutions of the problem. To find solutions to a problem it is then sufficient to use a satisfiability solver on a corresponding formula. Niemela, Marek, and Truszczynski coined answer set programming paradigm in~1999:  in this paradigm a logic program encodes problem specifications in a way that the answer sets of a logic program represent the solutions of the problem. As a result, to find solutions to a problem it is sufficient to use an answer set solver on a corresponding program. These parallels that we just draw between paradigms naturally bring up a question: what is a fundamental difference between the two? This paper takes a close look at this question.
Publication Date
December, 2016
Citation Information
Yuliya Lierler. "What is Answer Set Programming to Propositional Satisfiability" Constraints (2016)
Available at: http://works.bepress.com/yuliya_lierler/57/