Complexity of super-coherence problems in ASP

Mario Alviano, Wolfgang Faber, Stefan Woltran

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Adapting techniques from database theory in order to optimize Answer Set Programming (ASP) systems, and in particular the grounding components of ASP systems, is an important topic in ASP. In recent years, the Magic Set method has received some interest in this setting, and a variant of it, called Dynamic Magic Set, has been proposed for ASP. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all ASP programs. In a recent work, a large fragment of ASP programs, referred to as super-coherent programs, has been identified, for which Dynamic Magic Set is correct. The fragment contains all programs which possess at least one answer set, no matter which set of facts is added to them. Two open question remained: How complex is it to determine whether a given program is super-coherent? Does the restriction to super-coherent programs limit the problems that can be solved? Especially the first question turned out to be quite difficult to answer precisely. In this paper, we formally prove that deciding whether a propositional program is super-coherent is Π3P-complete in the disjunctive case, while it is Π2P-complete for normal programs. The hardness proofs are the difficult part in this endeavor: We proceed by characterizing the reductions by the models and reduct models which the ASP programs should have, and then provide instantiations that meet the given specifications. Concerning the second question, we show that all relevant ASP reasoning tasks can be transformed into tasks over super-coherent programs, although this transformation is more of theoretical than practical interest.

LanguageEnglish
Pages339-361
Number of pages23
JournalTheory and Practice of Logic Programming
Volume14
Issue number3
Early online date9 Aug 2013
DOIs
Publication statusPublished - May 2014
Externally publishedYes

Fingerprint

Computer systems programming
Answer Set Programming
Electric grounding
Computer programming
Hardness
Specifications
Fragment
Answer Sets
Reduct
Reasoning
Optimise
Query
Specification
Restriction

Cite this

Alviano, Mario ; Faber, Wolfgang ; Woltran, Stefan. / Complexity of super-coherence problems in ASP. In: Theory and Practice of Logic Programming. 2014 ; Vol. 14, No. 3. pp. 339-361.
@article{0fe9cab8ce2944948318efbc9f347073,
title = "Complexity of super-coherence problems in ASP",
abstract = "Adapting techniques from database theory in order to optimize Answer Set Programming (ASP) systems, and in particular the grounding components of ASP systems, is an important topic in ASP. In recent years, the Magic Set method has received some interest in this setting, and a variant of it, called Dynamic Magic Set, has been proposed for ASP. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all ASP programs. In a recent work, a large fragment of ASP programs, referred to as super-coherent programs, has been identified, for which Dynamic Magic Set is correct. The fragment contains all programs which possess at least one answer set, no matter which set of facts is added to them. Two open question remained: How complex is it to determine whether a given program is super-coherent? Does the restriction to super-coherent programs limit the problems that can be solved? Especially the first question turned out to be quite difficult to answer precisely. In this paper, we formally prove that deciding whether a propositional program is super-coherent is Π3P-complete in the disjunctive case, while it is Π2P-complete for normal programs. The hardness proofs are the difficult part in this endeavor: We proceed by characterizing the reductions by the models and reduct models which the ASP programs should have, and then provide instantiations that meet the given specifications. Concerning the second question, we show that all relevant ASP reasoning tasks can be transformed into tasks over super-coherent programs, although this transformation is more of theoretical than practical interest.",
keywords = "Answer Set Programming (ASP), coherence, complexity analysis, foundations, uniform equivalence",
author = "Mario Alviano and Wolfgang Faber and Stefan Woltran",
year = "2014",
month = "5",
doi = "10.1017/S147106841300001X",
language = "English",
volume = "14",
pages = "339--361",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "3",

}

Complexity of super-coherence problems in ASP. / Alviano, Mario; Faber, Wolfgang; Woltran, Stefan.

In: Theory and Practice of Logic Programming, Vol. 14, No. 3, 05.2014, p. 339-361.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Complexity of super-coherence problems in ASP

AU - Alviano, Mario

AU - Faber, Wolfgang

AU - Woltran, Stefan

PY - 2014/5

Y1 - 2014/5

N2 - Adapting techniques from database theory in order to optimize Answer Set Programming (ASP) systems, and in particular the grounding components of ASP systems, is an important topic in ASP. In recent years, the Magic Set method has received some interest in this setting, and a variant of it, called Dynamic Magic Set, has been proposed for ASP. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all ASP programs. In a recent work, a large fragment of ASP programs, referred to as super-coherent programs, has been identified, for which Dynamic Magic Set is correct. The fragment contains all programs which possess at least one answer set, no matter which set of facts is added to them. Two open question remained: How complex is it to determine whether a given program is super-coherent? Does the restriction to super-coherent programs limit the problems that can be solved? Especially the first question turned out to be quite difficult to answer precisely. In this paper, we formally prove that deciding whether a propositional program is super-coherent is Π3P-complete in the disjunctive case, while it is Π2P-complete for normal programs. The hardness proofs are the difficult part in this endeavor: We proceed by characterizing the reductions by the models and reduct models which the ASP programs should have, and then provide instantiations that meet the given specifications. Concerning the second question, we show that all relevant ASP reasoning tasks can be transformed into tasks over super-coherent programs, although this transformation is more of theoretical than practical interest.

AB - Adapting techniques from database theory in order to optimize Answer Set Programming (ASP) systems, and in particular the grounding components of ASP systems, is an important topic in ASP. In recent years, the Magic Set method has received some interest in this setting, and a variant of it, called Dynamic Magic Set, has been proposed for ASP. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all ASP programs. In a recent work, a large fragment of ASP programs, referred to as super-coherent programs, has been identified, for which Dynamic Magic Set is correct. The fragment contains all programs which possess at least one answer set, no matter which set of facts is added to them. Two open question remained: How complex is it to determine whether a given program is super-coherent? Does the restriction to super-coherent programs limit the problems that can be solved? Especially the first question turned out to be quite difficult to answer precisely. In this paper, we formally prove that deciding whether a propositional program is super-coherent is Π3P-complete in the disjunctive case, while it is Π2P-complete for normal programs. The hardness proofs are the difficult part in this endeavor: We proceed by characterizing the reductions by the models and reduct models which the ASP programs should have, and then provide instantiations that meet the given specifications. Concerning the second question, we show that all relevant ASP reasoning tasks can be transformed into tasks over super-coherent programs, although this transformation is more of theoretical than practical interest.

KW - Answer Set Programming (ASP)

KW - coherence

KW - complexity analysis

KW - foundations

KW - uniform equivalence

UR - http://www.scopus.com/inward/record.url?scp=84898486974&partnerID=8YFLogxK

U2 - 10.1017/S147106841300001X

DO - 10.1017/S147106841300001X

M3 - Article

VL - 14

SP - 339

EP - 361

JO - Theory and Practice of Logic Programming

T2 - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 3

ER -