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

Producción científica: Conference contribution › revisión exhaustiva

13 Citas (Scopus)

Resumen

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.

Idioma original	English
Título de la publicación alojada	Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings
Editores	Georg Gottlob, Daniela Inclezan, Marco Maratea
Páginas	373-386
Número de páginas	14
DOI	https://doi.org/10.1007/978-3-031-15707-3_29
Estado	Published - 2022
Evento	16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022 - Genoa, Italy Duración: sept 5 2022 → sept 9 2022

Serie de la publicación

Nombre	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen	13416 LNAI
ISSN (versión impresa)	0302-9743
ISSN (versión digital)	1611-3349

Conference

Conference	16th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2022
País/Territorio	Italy
Ciudad	Genoa
Período	9/5/22 → 9/9/22

Nota bibliográfica

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Acceder al documento

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

Otros archivos y enlaces

Citar esto

Amendola, G., Cuteri, B., Ricca, F., & Truszczynski, M. (2022). Solving Problems in the Polynomial Hierarchy with ASP(Q). En 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). En 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).

Producción científica: Conference contribution › revisión exhaustiva

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 - https://www.scopus.com/pages/publications/85138006390

UR - https://www.scopus.com/pages/publications/85138006390#tab=citedBy

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). En Gottlob G, Inclezan D, Maratea M, editores, 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)

Resumen

Serie de la publicación

Conference

Nota bibliográfica

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto