nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

Solving Problems in the Polynomial Hierarchy with ASP(Q)

verfasst von : Giovanni Amendola, Bernardo Cuteri, Francesco Ricca, Mirek Truszczynski

Erschienen in: Logic Programming and Nonmonotonic Reasoning

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel xASP: An Explanation Generation System for Answer Set Programming

Nächstes Kapitel A Practical Account into Counting Dung’s Extensions by Dynamic Programming

Alviano, M., Dodaro, C., Leone, N., Ricca, F.: Advances in WASP. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS (LNAI), vol. 9345, pp. 40–54. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_5CrossRef

Amendola, G., Dodaro, C., Faber, W., Ricca, F.: Paracoherent answer set computation. Artif. Intell. 299, 103519 (2021)MathSciNetCrossRefMATH

Amendola, G., Eiter, T., Fink, M., Leone, N., Moura, J.: Semi-equilibrium models for paracoherent answer set programs. Artif. Intell. 234, 219–271 (2016)MathSciNetCrossRefMATH

Amendola, G., Ricca, F., Truszczynski, M.: Beyond NP: quantifying over answer sets. Theory Pract. Log. Program. 19(5–6), 705–721 (2019)MathSciNetCrossRefMATH

Amendola, G., Ricca, F., Truszczynski, M.: New models for generating hard random boolean formulas and disjunctive logic programs. Artif. Intell. 279, 103185 (2020)MathSciNetCrossRefMATH

Bogaerts, B., Janhunen, T., Tasharrofi, S.: Stable-unstable semantics: beyond NP with normal logic programs. Theory Pract. Log. Program. 16(5–6), 570–586 (2016)MathSciNetCrossRefMATH

Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011)CrossRef

Calimeri, F., et al.: ASP-Core-2 input language format. Theory Pract. Log. Program. 20(2), 294–309 (2020)MathSciNetCrossRefMATH

Cao, F., Du, D.Z., Gao, B., Wan, P.J., Pardalos, P.M.: Minimax problems in combinatorial optimization. In: Du, DZ., Pardalos, P.M. (eds.) Minimax and Applications. Nonconvex Optimization and Its Applications, vol. 4, pp. 269–292. Springer, Cham (1995). https://doi.org/10.1007/978-1-4613-3557-3_18

10.

Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3), 374–425 (2001)CrossRef

11.

Dodaro, C., Galatà, G., Khan, M.K., Maratea, M., Porro, I.: Operating room (re)scheduling with bed management via ASP. Theory Pract. Log. Program. 22(2), 229–253 (2022)MathSciNetCrossRef

12.

Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321–358 (1995)MathSciNetCrossRefMATH

13.

Dunne, P.E., Bench-Capon, T.J.M.: Coherence in finite argument systems. Artif. Intell. 141(1/2), 187–203 (2002)MathSciNetCrossRefMATH

14.

Egly, U., Eiter, T., Tompits, H., Woltran, S.: Solving advanced reasoning tasks using quantified boolean formulas. In: Proceedings of IAAI 2000, pp. 417–422. AAAI Press/The MIT Press (2000)

15.

Eiter, T., Gottlob, G.: On the computational cost of disjunctive logic programming: propositional case. Ann. Math. Artif. Intell. 15(3–4), 289–323 (1995)MathSciNetCrossRefMATH

16.

Erdem, E., Gelfond, M., Leone, N.: Applications of answer set programming. AI Mag. 37(3), 53–68 (2016)

17.

Fandinno, J., Laferrière, F., Romero, J., Schaub, T., Son, T.C.: Planning with incomplete information in quantified answer set programming. Theory Pract. Log. Program. 21(5), 663–679 (2021)MathSciNetCrossRefMATH

18.

Gebser, M., Kaminski, R., Kaufmann, B., Romero, J., Schaub, T.: Progress in clasp Series 3. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS (LNAI), vol. 9345, pp. 368–383. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_31CrossRef

19.

Gebser, M., Maratea, M., Ricca, F.: The sixth answer set programming competition. J. Artif. Intell. Res. 60, 41–95 (2017)MathSciNetCrossRefMATH

20.

Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Comput. 9(3/4), 365–386 (1991)CrossRefMATH

21.

Janhunen, T.: Implementing stable-unstable semantics with ASPTOOLS and Clingo. In: Cheney, J., Perri, S. (eds.) PADL 2022. LNCS, vol. 13165, pp. 135–153. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-94479-7_9CrossRef

22.

Lifschitz, V.: Answer set programming and plan generation. Artif. Intell. 138(1–2), 39–54 (2002)MathSciNetCrossRefMATH

23.

Romero, J., Schaub, T., Son, T.C.: Generalized answer set planning with incomplete information. In: ASPOCP@LPNMR, vol. 1868 of CEUR WS, CEUR-WS.org (2017)

24.

Sakama, C., Inoue, K.: Paraconsistent stable semantics for extended disjunctive programs. J. Log. Comput. 5(3), 265–285 (1995)MathSciNetCrossRefMATH

Titel: Solving Problems in the Polynomial Hierarchy with ASP(Q)
verfasst von: Giovanni Amendola
Bernardo Cuteri
Francesco Ricca
Mirek Truszczynski
Verlag: Springer International Publishing
Buch: Logic Programming and Nonmonotonic Reasoning
Print ISBN: 978-3-031-15706-6

Electronic ISBN: 978-3-031-15707-3

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-031-15707-3_29

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner