Answer set programming (ASP; Gelfond et al. 1988) is a declarative formalism that allows to express relations between truth values of propositions by rules of the form Such a rule intuitively states that whenever is true, proposition should be true as well. ASP di ers from other logic programming formalisms such as Prolog by its declarative treatment of negation-as-failure, an important construct by which statements are considered to be false when they cannot be proven to hold. For example, consider the problem where a seat s has to be assigned to one of two persons p1 and p2. This can be done using the following program, where sit(p; s) denotes that person p is sitting on seat s:
sit (p1,S)