Semantical characterizations and complexity of equivalences in answer set programming
From MaRDI portal
Abstract: In recent research on non-monotonic logic programming, repeatedly strong equivalence of logic programs P and Q has been considered, which holds if the programs P union R and Q union R have the same answer sets for any other program R. This property strengthens equivalence of P and Q with respect to answer sets (which is the particular case for R is the empty set), and has its applications in program optimization, verification, and modular logic programming. In this paper, we consider more liberal notions of strong equivalence, in which the actual form of R may be syntactically restricted. On the one hand, we consider uniform equivalence, where R is a set of facts rather than a set of rules. This notion, which is well known in the area of deductive databases, is particularly useful for assessing whether programs P and Q are equivalent as components of a logic program which is modularly structured. On the other hand, we consider relativized notions of equivalence, where R ranges over rules over a fixed alphabet, and thus generalize our results to relativized notions of strong and uniform equivalence. For all these notions, we consider disjunctive logic programs in the propositional (ground) case, as well as some restricted classes, provide semantical characterizations and analyze the computational complexity. Our results, which naturally extend to answer set semantics for programs with strong negation, complement the results on strong equivalence of logic programs and pave the way for optimizations in answer set solvers as a tool for input-based problem solving.
Recommendations
- Logics in Artificial Intelligence
- scientific article; zbMATH DE number 2090116
- A characterization of answer sets for logic programs
- Equivalence Between Answer-Set Programs Under (Partially) Fixed Input
- Equivalence between answer-set programs under (partially) fixed input
- Logic Programming
- Semantics and complexity of recursive aggregates in answer set programming
- Alternative Characterizations for Program Equivalence under Answer-Set Semantics Based on Unfounded Sets
- Complexity results for answer set programming with bounded predicate arities and implications
- scientific article; zbMATH DE number 1882048
Cited in
(47)- Equivalence between answer-set programs under (partially) fixed input
- On syntactic forgetting under uniform equivalence
- A polynomial reduction of forks into logic programs
- On the limits of forgetting in answer set programming
- Deciding equivalence of separated non-nested attribute systems in polynomial time
- Characterising relativised strong equivalence with projection for non-ground answer-set programs
- Query inseparability for \(\mathcal{ALC}\) ontologies
- A general notion of equivalence for abstract argumentation
- Forgetting auxiliary atoms in forks
- Semantic forgetting in answer set programming
- Strong and uniform equivalence of nonmonotonic theories -- an algebraic approach
- A characterization of answer sets for logic programs
- Interlinking logic programs and argumentation frameworks
- Equivalence Between Answer-Set Programs Under (Partially) Fixed Input
- Strong equivalence of qualitative optimization problems
- The Complexity Boundary of Answer Set Programming with Generalized Atoms under the FLP Semantics
- Applying visible strong equivalence in answer-set program transformations
- Preserving strong equivalence while forgetting
- Characterising equilibrium logic and nested logic programs: Reductions and complexity,
- Well-Founded and Partial Stable Semantics Logical Aspects
- Formal Properties of Modularisation
- Answer Set Programming: A Primer
- Casting Away Disjunction and Negation under a Generalisation of Strong Equivalence with Projection
- Relativized hyperequivalence of logic programs for modular programming
- Characterizing strong equivalence for argumentation frameworks
- Model-based recasting in answer-set programming
- Characterizing and extending answer set semantics using possibility theory
- Dual-normal logic programs -- the forgotten class
- Fuzzy answer set computation via satisfiability modulo theories
- On uniform equivalence of epistemic logic programs
- Logic Programming
- On graph equivalences preserved under extensions
- Logics in Artificial Intelligence
- Logic Programming and Nonmonotonic Reasoning
- Complexity of Rule Redundancy in Non-ground Answer-Set Programming over Finite Domains
- Generality Relations in Answer Set Programming
- A common view on strong, uniform, and other notions of equivalence in answer-set programming
- Logic Programming
- Equivalences in Answer-Set Programming by Countermodels in the Logic of Here-and-There
- Relativized Hyperequivalence of Logic Programs for Modular Programming
- Program Correspondence under the Answer-Set Semantics: The Non-ground Case
- On the strong equivalences for \(\mathrm{LP^{MLN}}\) programs
- Abstraction for non-ground answer set programs
- 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
- Forgetting in answer set programming -- a survey
- Strong order equivalence
This page was built for publication: Semantical characterizations and complexity of equivalences in answer set programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277782)
