Solving Problems in the Polynomial Hierarchy with ASP(Q)

Giovanni Amendola, Bernardo Cuteri, Francesco Ricca, Mirek Truszczynski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Answer Set Programming with Quantifiers ASP(Q) is a recent extension of Answer Set Programming (ASP) that allows one to model problems from the entire polynomial hierarchy. Earlier work focused on demonstrating modeling capabilities of ASP(Q). In this paper, we propose a modular ASP(Q) solver that translates a quantified ASP program together with a given data instance into a Quantified Boolean Formula (QBF) to be solved by any QBF solver. We evaluate the performance of our solver on several instances and with different back-end QBF solvers, demonstrating the efficacy of ASP(Q) as a tool for rapid modeling and solving of complex combinatorial problems. The benchmark problems we use include two new ones, Argumentation Coherence and Para-coherent ASP, for which we develop elegant ASP(Q) encodings.

Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings
EditorsGeorg Gottlob, Daniela Inclezan, Marco Maratea
Pages373-386
Number of pages14
DOIs
StatePublished - 2022
Event16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022 - Genoa, Italy
Duration: Sep 5 2022Sep 9 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13416 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022
Country/TerritoryItaly
CityGenoa
Period9/5/229/9/22

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

  • Answer Set Programming
  • QBF
  • Quantifiers

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Solving Problems in the Polynomial Hierarchy with ASP(Q)'. Together they form a unique fingerprint.

Cite this