An Abstract, Logical Approach to Characterizing Strong Equivalence in Non-monotonic Knowledge Representation Formalisms

Ringo BaumannRingo Baumann, Hannes StraßHannes Straß

Ringo Baumann, Hannes Straß
An Abstract, Logical Approach to Characterizing Strong Equivalence in Non-monotonic Knowledge Representation Formalisms
Artificial Intelligence, 305:103680, April 2022

Details
Bibtex

KurzfassungAbstract
Two knowledge bases are strongly equivalent if and only if they are mutually interchangeable in arbitrary contexts. For classical logic, this notion of equivalence coincides with standard equivalence (having the same models). However, there are also knowledge representation formalisms for which strong and standard equivalence are different, for example logic programs under the stable model semantics, Reiter's default logic, or Dung's argumentation frameworks. In these settings, it is important to know how strong equivalence can be characterized, that is, whether there is a characterizing formalism whose ordinary equivalence coincides with strong equivalence in the characterized formalism. For example, strong equivalence for logic programs under stable models can be characterized by so-called SE-models. In this paper, we show that every knowledge representation formalism that allows for a notion of strong equivalence on its finite knowledge bases also possesses a canonical characterizing formalism. In particular, we argue that those characterizing formalisms can be seen as classical, monotonic logics. As a corollary of our results, we obtain the first semantical characterization of strong equivalence in argumentation frameworks.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@article{BS2022,
  author    = {Ringo Baumann and Hannes Stra{\ss}},
  title     = {An Abstract, Logical Approach to Characterizing Strong
               Equivalence in Non-monotonic Knowledge Representation Formalisms},
  journal   = {Artificial Intelligence},
  volume    = {305},
  publisher = {Elsevier},
  year      = {2022},
  month     = {April},
  pages     = {103680},
  doi       = {https://doi.org/10.1016/j.artint.2022.103680}
}