Semantical characterizations and complexity of equivalences in answer set programming

DOI10.1145/1243996.1244000zbMath1367.68031arXivcs/0502078OpenAlexW1971626643MaRDI QIDQ5277782

Thomas Eiter, Michael Fink, Stefan Woltran

Publication date: 12 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0502078

zbMATH Keywords

computational complexity program optimization stable models answer set semantics uniform equivalence strong equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semantics in the theory of computing (68Q55) Logic programming (68N17)

Related Items (29)

Applying Visible Strong Equivalence in Answer-Set Program Transformations ⋮ A polynomial reduction of forks into logic programs ⋮ Characterising equilibrium logic and nested logic programs: Reductions and complexity, ⋮ Strong order equivalence ⋮ Strong and uniform equivalence of nonmonotonic theories -- an algebraic approach ⋮ Semantic forgetting in answer set programming ⋮ Preserving Strong Equivalence while Forgetting ⋮ Unnamed Item ⋮ Model-based recasting in answer-set programming ⋮ Dual-normal logic programs – the forgotten class ⋮ Fuzzy answer set computation via satisfiability modulo theories ⋮ Logic-based ontology comparison and module extraction, with an application to DL-Lite ⋮ Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs ⋮ Characterizing strong equivalence for argumentation frameworks ⋮ Interlinking logic programs and argumentation frameworks ⋮ On the limits of forgetting in answer set programming ⋮ On graph equivalences preserved under extensions ⋮ Equivalence between answer-set programs under (partially) fixed input ⋮ Abstraction for non-ground answer set programs ⋮ Formal Properties of Modularisation ⋮ On syntactic forgetting under uniform equivalence ⋮ Answer Set Programming: A Primer ⋮ Well-Founded and Partial Stable Semantics Logical Aspects ⋮ Relativized hyperequivalence of logic programs for modular programming ⋮ Query inseparability for \(\mathcal{ALC}\) ontologies ⋮ A general notion of equivalence for abstract argumentation ⋮ Forgetting auxiliary atoms in forks ⋮ Equivalences in Answer-Set Programming by Countermodels in the Logic of Here-and-There ⋮ Relativized Hyperequivalence of Logic Programs for Modular Programming

This page was built for publication: Semantical characterizations and complexity of equivalences in answer set programming