Stable-unstable semantics

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en Bogaerts, Bart Janhunen, Tomi Tasharrofi, Shahab 2019-01-14T09:20:43Z 2019-01-14T09:20:43Z 2016-09-01
dc.identifier.citation Bogaerts , B , Janhunen , T & Tasharrofi , S 2016 , ' Stable-unstable semantics : Beyond NP with normal logic programs ' Theory and Practice of Logic Programming , vol. 16 , no. 5-6 , pp. 570-586 . DOI: 10.1017/S1471068416000387 en
dc.identifier.issn 1471-0684
dc.identifier.issn 1475-3081
dc.identifier.other PURE UUID: 446e8a01-900d-4ba8-b143-1795648500c6
dc.identifier.other PURE ITEMURL:
dc.identifier.other PURE LINK:
dc.identifier.other PURE FILEURL:
dc.description.abstract 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-levellanguages 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. en
dc.format.extent 17
dc.format.extent 570-586
dc.format.mimetype application/pdf
dc.language.iso en en
dc.relation.ispartofseries Theory and Practice of Logic Programming en
dc.relation.ispartofseries Volume 16, issue 5-6 en
dc.rights openAccess en
dc.subject.other Theoretical Computer Science en
dc.subject.other Software en
dc.subject.other Hardware and Architecture en
dc.subject.other Computational Theory and Mathematics en
dc.subject.other Artificial Intelligence en
dc.subject.other 113 Computer and information sciences en
dc.title Stable-unstable semantics en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.subject.keyword disjunctive logic programming
dc.subject.keyword polynomial hierarchy
dc.subject.keyword quantified Boolean formulas
dc.subject.keyword Theoretical Computer Science
dc.subject.keyword Software
dc.subject.keyword Hardware and Architecture
dc.subject.keyword Computational Theory and Mathematics
dc.subject.keyword Artificial Intelligence
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201901141128
dc.identifier.doi 10.1017/S1471068416000387
dc.type.version acceptedVersion

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication


My Account