We build upon recent work by Lierler that denes an abstract framework for describing the algorithm underlying many of the existing answer set solvers (for answer set programs, based upon the Answer Set Semantics), considering in particular Smodels and SUP. We dene a particular class of programs, called AOH, and prove that the computation that the abstract solver performs actually represents a lower bound for deciding inconsistency of logic programs under the Answer Set Semantics. The main result is that for a given AOH program with n atoms, an algorithm that conforms to Lierler's abstract model needs (n) steps before exiting with failure (no answer set exists). We argue that our result holds for every logic program that, like AOH programs, contains cyclic denitions and rules that can be seen as connecting the cycles.

A Lower Bound for Answer Set Solver Computation

PROVETTI, Alessandro
2010-01-01

Abstract

We build upon recent work by Lierler that denes an abstract framework for describing the algorithm underlying many of the existing answer set solvers (for answer set programs, based upon the Answer Set Semantics), considering in particular Smodels and SUP. We dene a particular class of programs, called AOH, and prove that the computation that the abstract solver performs actually represents a lower bound for deciding inconsistency of logic programs under the Answer Set Semantics. The main result is that for a given AOH program with n atoms, an algorithm that conforms to Lierler's abstract model needs (n) steps before exiting with failure (no answer set exists). We argue that our result holds for every logic program that, like AOH programs, contains cyclic denitions and rules that can be seen as connecting the cycles.
2010
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/11570/1903819
 Attenzione

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

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