Solving Problems in the Polynomial Hierarchy with ASP(Q)

Giovanni Amendola; Bernardo Cuteri; Francesco Ricca; Mirek Truszczynski

doi:10.1007/978-3-031-15707-3_29

Solving Problems in the Polynomial Hierarchy with ASP(Q)

Giovanni Amendola, Bernardo Cuteri, Francesco Ricca, Mirek Truszczynski

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

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 language	English
Title of host publication	Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings
Editors	Georg Gottlob, Daniela Inclezan, Marco Maratea
Pages	373-386
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-031-15707-3_29
State	Published - 2022
Event	16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022 - Genoa, Italy Duration: Sep 5 2022 → Sep 9 2022

Publication series

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

Conference

Conference	16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022
Country/Territory	Italy
City	Genoa
Period	9/5/22 → 9/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
General Computer Science

Access to Document

10.1007/978-3-031-15707-3_29

Cite this

Amendola, G., Cuteri, B., Ricca, F., & Truszczynski, M. (2022). Solving Problems in the Polynomial Hierarchy with ASP(Q). In G. Gottlob, D. Inclezan, & M. Maratea (Eds.), Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings (pp. 373-386). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13416 LNAI). https://doi.org/10.1007/978-3-031-15707-3_29

Amendola, Giovanni ; Cuteri, Bernardo ; Ricca, Francesco et al. / Solving Problems in the Polynomial Hierarchy with ASP(Q). Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. editor / Georg Gottlob ; Daniela Inclezan ; Marco Maratea. 2022. pp. 373-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{eac3bf4b5f6b43dd9e13fc35861c4ff8,

title = "Solving Problems in the Polynomial Hierarchy with ASP(Q)",

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.",

keywords = "Answer Set Programming, QBF, Quantifiers",

author = "Giovanni Amendola and Bernardo Cuteri and Francesco Ricca and Mirek Truszczynski",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022 ; Conference date: 05-09-2022 Through 09-09-2022",

year = "2022",

doi = "10.1007/978-3-031-15707-3_29",

language = "English",

isbn = "9783031157066",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "373--386",

editor = "Georg Gottlob and Daniela Inclezan and Marco Maratea",

booktitle = "Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings",

}

Amendola, G, Cuteri, B, Ricca, F & Truszczynski, M 2022, Solving Problems in the Polynomial Hierarchy with ASP(Q). in G Gottlob, D Inclezan & M Maratea (eds), Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13416 LNAI, pp. 373-386, 16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022, Genoa, Italy, 9/5/22. https://doi.org/10.1007/978-3-031-15707-3_29

Solving Problems in the Polynomial Hierarchy with ASP(Q). / Amendola, Giovanni; Cuteri, Bernardo; Ricca, Francesco et al.
Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. ed. / Georg Gottlob; Daniela Inclezan; Marco Maratea. 2022. p. 373-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13416 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Solving Problems in the Polynomial Hierarchy with ASP(Q)

AU - Amendola, Giovanni

AU - Cuteri, Bernardo

AU - Ricca, Francesco

AU - Truszczynski, Mirek

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Answer Set Programming

KW - QBF

KW - Quantifiers

UR - http://www.scopus.com/inward/record.url?scp=85138006390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85138006390&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-15707-3_29

DO - 10.1007/978-3-031-15707-3_29

M3 - Conference contribution

AN - SCOPUS:85138006390

SN - 9783031157066

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 373

EP - 386

BT - Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings

A2 - Gottlob, Georg

A2 - Inclezan, Daniela

A2 - Maratea, Marco

T2 - 16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022

Y2 - 5 September 2022 through 9 September 2022

ER -

Amendola G, Cuteri B, Ricca F, Truszczynski M. Solving Problems in the Polynomial Hierarchy with ASP(Q). In Gottlob G, Inclezan D, Maratea M, editors, Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings. 2022. p. 373-386. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-15707-3_29

Solving Problems in the Polynomial Hierarchy with ASP(Q)

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this