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
(46)- A characterization of answer sets for logic programs
- The Complexity Boundary of Answer Set Programming with Generalized Atoms under the FLP Semantics
- Query inseparability for \(\mathcal{ALC}\) ontologies
- Logic Programming
- Model-based recasting in answer-set programming
- Logic-based ontology comparison and module extraction, with an application to DL-Lite
- Program Correspondence under the Answer-Set Semantics: The Non-ground Case
- Relativized hyperequivalence of logic programs for modular programming
- Complexity of Rule Redundancy in Non-ground Answer-Set Programming over Finite Domains
- Answer Set Programming: A Primer
- Characterising equilibrium logic and nested logic programs: Reductions and complexity,
- On graph equivalences preserved under extensions
- A common view on strong, uniform, and other notions of equivalence in answer-set programming
- A general notion of equivalence for abstract argumentation
- Formal Properties of Modularisation
- Characterizing and extending answer set semantics using possibility theory
- Abstraction for non-ground answer set programs
- Strong order equivalence
- Casting Away Disjunction and Negation under a Generalisation of Strong Equivalence with Projection
- Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs
- Characterizing strong equivalence for argumentation frameworks
- Fuzzy answer set computation via satisfiability modulo theories
- A polynomial reduction of forks into logic programs
- Forgetting in answer set programming -- a survey
- Relativized Hyperequivalence of Logic Programs for Modular Programming
- On the strong equivalences for \(\mathrm{LP^{MLN}}\) programs
- Logic Programming
- Generality Relations in Answer Set Programming
- On uniform equivalence of epistemic logic programs
- Equivalence between answer-set programs under (partially) fixed input
- Equivalences in Answer-Set Programming by Countermodels in the Logic of Here-and-There
- Interlinking logic programs and argumentation frameworks
- Preserving strong equivalence while forgetting
- Forgetting auxiliary atoms in forks
- On syntactic forgetting under uniform equivalence
- Well-Founded and Partial Stable Semantics Logical Aspects
- On the limits of forgetting in answer set programming
- Strong and uniform equivalence of nonmonotonic theories -- an algebraic approach
- Logics in Artificial Intelligence
- Deciding equivalence of separated non-nested attribute systems in polynomial time
- Strong equivalence of qualitative optimization problems
- Logic Programming and Nonmonotonic Reasoning
- Equivalence Between Answer-Set Programs Under (Partially) Fixed Input
- Semantic forgetting in answer set programming
- Applying visible strong equivalence in answer-set program transformations
- Dual-normal logic programs -- the forgotten class
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)
