The support for function symbols in logic programming under Answer Set Programming semantics (ASP) allows to overcome some modeling limitations of traditional 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. Thus, the research is lately focusing on finding proper subclasses of ASP programs with functions for which decidability of inference is guaranteed. The two major proposals so far, finitary programs and finitely-ground programs, are complementary, to some extent; indeed, the former are conceived for allowing decidable querying (using a top-down evaluation strategy), while the latter for allowing finite model computation (using 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. However, many programs lie outside this class, such as, in general, positive finitary programs. Indeed, ground queries over such programs can be easily answered by means of top-down techniques; bottom-up approaches, instead, are, in general, unsuitable. In this work we present a proper adaptation of the magic-sets technique that aims at making query answering over positive finitary (normal) programs feasible by means of bottom-up techniques, i.e., those all current ASP systems rely on.

Bottom-up Evaluation of Finitely Recursive Queries

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

Abstract

The support for function symbols in logic programming under Answer Set Programming semantics (ASP) allows to overcome some modeling limitations of traditional 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. Thus, the research is lately focusing on finding proper subclasses of ASP programs with functions for which decidability of inference is guaranteed. The two major proposals so far, finitary programs and finitely-ground programs, are complementary, to some extent; indeed, the former are conceived for allowing decidable querying (using a top-down evaluation strategy), while the latter for allowing finite model computation (using 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. However, many programs lie outside this class, such as, in general, positive finitary programs. Indeed, ground queries over such programs can be easily answered by means of top-down techniques; bottom-up approaches, instead, are, in general, unsuitable. In this work we present a proper adaptation of the magic-sets technique that aims at making query answering over positive finitary (normal) programs feasible by means of bottom-up techniques, i.e., those all current ASP systems rely on.
answer set programming; nonmonotonic reasoning; 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: https://hdl.handle.net/20.500.11770/182027
 Attenzione

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

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