The support for function symbols in logic programming under answer set semantics allows to overcome some modeling limitations of traditional Answer Set Programming (ASP) systems, such as the inability of handling infinite domains. On the other hand, admitting function symbols in ASP makes inference undecidable in the general case. Lately, the research community is focusing on finding proper subclasses for which decidability of inference is guaranteed. The two major proposals, so far, are finitary programs and finitely-ground programs. These two proposals are somehow complementary: indeed, the former is conceived to allow decidable querying (by means of a top-down evaluation strategy), while the latter supports the computability of answer-sets (by means of a bottom-up evaluation strategy). One of the main advantages of finitely-ground programs is that they can be "directly" evaluated by current ASP systems, which are based on a bottom-up computational model. However, there are also some interesting programs which are suitable for top-down query evaluation; but do not fall in the class of finitely-ground programs. In this paper, we focus on disjunctive finitely-recursive positive (DFRP) programs. We present a proper adaptation of the magic-sets technique for DFRP programs, which ensures query equivalence under both brave and cautious reasoning. We show that, if the input program is DFRP, then its magic-set rewriting is guaranteed to be finitely ground. Thus, reasoning on DFRP programs turns out to be decidable, and we provide an effective method for its computation on the ASP system DLV.

Magic Sets for the Bottom-Up Evaluation of Finitely Recursive Programs

CALIMERI, Francesco;COZZA S;IANNI, Giovambattista;LEONE, Nicola
2009

Abstract

The support for function symbols in logic programming under answer set semantics allows to overcome some modeling limitations of traditional Answer Set Programming (ASP) systems, such as the inability of handling infinite domains. On the other hand, admitting function symbols in ASP makes inference undecidable in the general case. Lately, the research community is focusing on finding proper subclasses for which decidability of inference is guaranteed. The two major proposals, so far, are finitary programs and finitely-ground programs. These two proposals are somehow complementary: indeed, the former is conceived to allow decidable querying (by means of a top-down evaluation strategy), while the latter supports the computability of answer-sets (by means of a bottom-up evaluation strategy). One of the main advantages of finitely-ground programs is that they can be "directly" evaluated by current ASP systems, which are based on a bottom-up computational model. However, there are also some interesting programs which are suitable for top-down query evaluation; but do not fall in the class of finitely-ground programs. In this paper, we focus on disjunctive finitely-recursive positive (DFRP) programs. We present a proper adaptation of the magic-sets technique for DFRP programs, which ensures query equivalence under both brave and cautious reasoning. We show that, if the input program is DFRP, then its magic-set rewriting is guaranteed to be finitely ground. Thus, reasoning on DFRP programs turns out to be decidable, and we provide an effective method for its computation on the ASP system DLV.
978-3-642-04237-9
logic programming; nonmonotonic reasoning; answer set programming; magic sets; artificial intelligence
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: http://hdl.handle.net/20.500.11770/161927
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 3
social impact