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 define a particular class of programs 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. For that class of programs, given a program composed of n atoms a solver adopting this algorithm must perform no less than n steps. We then argue that this result can be extrapolated to every logic program.

A Lower-bound for Answer Set solver Computation

PROVETTI, Alessandro
2009

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 define a particular class of programs 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. For that class of programs, given a program composed of n atoms a solver adopting this algorithm must perform no less than n steps. We then argue that this result can be extrapolated to every logic program.
File in questo prodotto:
File Dimensione Formato  
15_LANMR09_12.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 275.76 kB
Formato Adobe PDF
275.76 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/11570/1903821
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact