Answer Set Programming (ASP) is a logic-based knowledge representation framework, supporting - among other reasoning modes - the central task of query answering. In the propositional case, query answering amounts to computing cautious consequences of the input program among the atoms in a given set of candidates, where a cautious consequence is an atom belonging to all stable models. Currently, the most efficient algorithms either iteratively verify the existence of a stable model of the input program extended with the complement of one candidate, where the candidate is heuristically selected, or introduce a clause enforcing the falsity of at least one candidate, so that the solver is free to choose which candidate to falsify at any time during the computation of a stable model. This paper introduces new algorithms for the computation of cautious consequences, with the aim of driving the solver to search for stable models discarding more candidates. Specifically, one of such algorithms enforces minimality on the set of true candidates, where different notions of minimality can be used, and another takes advantage of unsatisfiable cores computation. The algorithms are implemented in wasp, and experiments on benchmarks from the latest ASP competitions show that the new algorithms perform better than the state of the art. Copyright © Cambridge University Press 2018.

Cautious reasoning in ASP via minimal models and unsatisfiable cores

DODARO, CARMINE;Marco Maratea;
2018

Abstract

Answer Set Programming (ASP) is a logic-based knowledge representation framework, supporting - among other reasoning modes - the central task of query answering. In the propositional case, query answering amounts to computing cautious consequences of the input program among the atoms in a given set of candidates, where a cautious consequence is an atom belonging to all stable models. Currently, the most efficient algorithms either iteratively verify the existence of a stable model of the input program extended with the complement of one candidate, where the candidate is heuristically selected, or introduce a clause enforcing the falsity of at least one candidate, so that the solver is free to choose which candidate to falsify at any time during the computation of a stable model. This paper introduces new algorithms for the computation of cautious consequences, with the aim of driving the solver to search for stable models discarding more candidates. Specifically, one of such algorithms enforces minimality on the set of true candidates, where different notions of minimality can be used, and another takes advantage of unsatisfiable cores computation. The algorithms are implemented in wasp, and experiments on benchmarks from the latest ASP competitions show that the new algorithms perform better than the state of the art. Copyright © Cambridge University Press 2018.
File in questo prodotto:
File Dimensione Formato  
cautious_reasoning_in_asp_via_minimal_models_and_unsatisfiable_cores.pdf

accesso chiuso

Tipologia: Documento in versione editoriale
Dimensione 346.98 kB
Formato Adobe PDF
346.98 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11567/921450
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 8
social impact