Answer Set Programming - Reasoning Web - page 175

cost) or explicit domain restrictions, thus allowing computability of answer sets and/or
decidability of querying.
Semantically restricted fragments ,suchas finitely ground programs [53], finitary
programs [58,59], disjunctive finitely-recursive programs [60] and queries [61,62]; with
respect to syntactically restricted fragments, these approaches aim at identifying broader
classes of programs for which computational tasks such as querying are decidable.
However, deciding the membership of a given program in these fragments is unde-
cidable in general.
There have been a few other proposals that treat function symbols not in the tradi-
tional logic programming sense, but as in classical logic, where most prominently the
unique names assumption does not hold. We refer to [63] for an overview.
Concerning existential quantifiers in rule heads, most proposals are confined to posi-
tive, non-disjunctive programs, often referred to as Datalog ± . The decidable subclasses
in this case rely on four main syntactic paradigms, called guardedness [64], weak-
acyclicity [65], stickiness [66,67], and shyness [68]. Extensions of these decidable
classes to positive, but disjunctive programs have been proposed in [69], [70], and [71].
A condition which combines weak acyclicity and guardedness has been proposed in
[72]. Guardedness has been extended to stratified negation in [73].
Arbitrary Formulas as Programs. There have been several attempts at generalizing the
input language to arbitrary formulas, rather than rules, with the intention of identifying
the “ASP logic.” Pearce had provided equilibrium logic in the 1990s [36], but it was
confined to propositional logic and had only one kind of negation (negation as failure).
This logic has more recently been extended to quantified equilibrium logic in [74].
Moreover, there were attempts at defining semantics of arbitrary formulas by means
of a second-order sentence reminiscent of circumscription. This had first been done
for propositional formulas [75], and was later extended to first-order formulas [76]. In
contrast to the languages discussed in the previous sections, the goal here is to define
an ASP semantics for languages that are as general as possible. Reasoning tasks for
first-order theories clearly suffer from undecidability issues.
Preference Handling. ASP programs usually follow a “guess and check” programming
pattern (see Section 4), where a set of rules (the guessing part) is used to guess a solution
(or equivalently, to generate answer set candidates); while another set of rules, called
checking part, is added to discard solutions which are not admissible. This methodology
allows the programmer to distinguish between solutions and non-solutions. However,
in many realistic applications the possibility to make more fine grained distinctions is
required; and, in particular, distinctions between more and less preferred solutions are
needed (see [77] for a discussion). For this reason, there has been a substantial amount
of work on extending ASP programs with preferences, and in particular, the major fo-
cus has been on qualitative approaches. This stems from the fact that for a variety of
applications numerical information is hard to obtain (preference elicitation is rather
difficult) and often turns out to be unnecessary (see [77]). Still, language extensions
based on quantitative information, such as weak constraints mentioned above, emulate
qualitative preferences under certain conditions, and vice versa.