Stable-Unstable Semantics: Beyond NP with Normal Logic Programs
  Standard answer set programming (ASP) targets at solving search problems from
the first level of the polynomial time hierarchy (PH). Tackling search problems
beyond NP using ASP is less straightforward. The class of disjunctive logic
programs offers the most prominent way of reaching the second level of the PH,
but encoding respective hard problems as disjunctive programs typically
requires sophisticated techniques such as saturation or meta-interpretation.
The application of such techniques easily leads to encodings that are
inaccessible to non-experts. Furthermore, while disjunctive ASP solvers often
rely on calls to a (co-)NP oracle, it may be difficult to detect from the input
program where the oracle is being accessed. In other formalisms, such as
Quantified Boolean Formulas (QBFs), the interface to the underlying oracle is
more transparent as it is explicitly recorded in the quantifier prefix of a
formula. On the other hand, ASP has advantages over QBFs from the modeling
perspective. The rich high-level languages such as ASP-Core-2 offer a wide
variety of primitives that enable concise and natural encodings of search
problems. In this paper, we present a novel logic programming--based modeling
paradigm that combines the best features of ASP and QBFs. We develop so-called
combined logic programs in which oracles are directly cast as (normal) logic
programs themselves. Recursive incarnations of this construction enable logic
programming on arbitrarily high levels of the PH. We develop a proof-of-concept
implementation for our new paradigm.
  This paper is under consideration for acceptance in TPLP.
