Simulating Sets in Answer Set Programming

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Abstract

We study the extension of non-monotonic disjunctive logic programs with terms that represent sets of constants, called DLP(S), under the stable model semantics. This strictly increases expressive power, but keeps reasoning decidable, though cautious entailment is CONEXPTIMENP-complete, even for data complexity. We present two new reasoning methods for DLP(S): a semantics-preserving translation of DLP(S) to logic programming with function symbols, which can take advantage of lazy grounding techniques, and a ground-and-solve approach that uses non-monotonic existential rules in the grounding stage. Our evaluation considers problems of ontological reasoning that are not in scope for traditional ASP (unless EXPTIME = ΠP2), and we find that our new existential-rule grounding performs well in comparison with native implementations of set terms in ASP.

Details

Original languageEnglish
Title of host publicationProceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022)
EditorsLuc De Raedt
Publisherijcai.org
Pages2634–2640
Number of pages7
Publication statusPublished - 2022
Peer-reviewedYes

External IDs

Mendeley 2b50c3e5-8911-3fd4-a6ad-79061ac809c1
unpaywall 10.24963/ijcai.2022/365