Answer set programming

Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop). In a more general sense, ASP includes all applications of answer sets to knowledge representation and the use of Prolog-style query evaluation for solving problems arising in these applications. An early example of answer set programming was the planning method proposed in 1997 by Dimopoulos, Nebel and Köhler. Their approach is based on the relationship between plans and stable models. In 1998 Soininen and Niemelä applied what is now known as answer set programming to the problem of product configuration. In 1999, the term "answer set programming" appeared for the first time in a book The Logic Programming Paradigm as the title of a collection of two papers. The first of these papers identified the use of answer set solvers for search as a new programming paradigm. That same year Niemelä also proposed "logic programs with stable model semantics" as a new paradigm. Lparse is the name of the program that was originally created as a grounding tool (front-end) for the answer set solver smodels. The language that Lparse accepts is now commonly called AnsProlog, short for Answer Set Programming in Logic. It is now used in the same way in many other answer set solvers, including assat, clasp, cmodels, gNt, nomore++ and pbmodels. (dlv is an exception; the syntax of ASP programs written for dlv is somewhat different.) An AnsProlog program consists of rules of the form :- . The symbol :- ("if") is dropped if is empty; such rules are called facts.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (6)

Related lectures (8)

Answer set programming

Negation as failure

Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive (i.e. that is assumed not to hold) from failure to derive . Note that can be different from the statement of the logical negation of , depending on the completeness of the inference algorithm and thus also on the formal logic system. Negation as failure has been an important feature of logic programming since the earliest days of both Planner and Prolog. In Prolog, it is usually implemented using Prolog's extralogical constructs.

Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other.

Exam Instructions & Big Data Infrastructures CS-422: Database systems

Covers exam instructions and big data infrastructures, including types of questions and fault tolerance.

Initial BFS MATH-261: Discrete optimization

Explores finding the initial Basic Feasible Solution (BFS) in a linear program.

Choosing a Step Size MATH-512: Optimization on manifolds MOOC: Introduction to optimization on smooth manifolds: first order methods

Explores choosing a step size in optimization on manifolds, including backtracking line-search and the Armijo method.