Strong Equivalence for Epistemic Logic Programs Made Easy

Authors

  • Wolfgang Faber Alpen-Adria-Universität Klagenfurt
  • Michael Morak Vienna University of Technology
  • Stefan Woltran Vienna University of Technology

DOI:

https://doi.org/10.1609/aaai.v33i01.33012809

Abstract

Epistemic Logic Programs (ELPs), that is, Answer Set Programming (ASP) extended with epistemic operators, have received renewed interest in recent years, which led to a flurry of new research, as well as efficient solvers. An important question is under which conditions a sub-program can be replaced by another one without changing the meaning, in any context. This problem is known as strong equivalence, and is well-studied for ASP. For ELPs, this question has been approached by embedding them into epistemic extensions of equilibrium logics. In this paper, we consider a simpler, more direct characterization that is directly applicable to the language used in state-of-the-art ELP solvers. This also allows us to give tight complexity bounds, showing that strong equivalence for ELPs remains coNP-complete, as for ASP. We further use our results to provide syntactic characterizations for tautological rules and rule subsumption for ELPs.

Downloads

Published

2019-07-17

How to Cite

Faber, W., Morak, M., & Woltran, S. (2019). Strong Equivalence for Epistemic Logic Programs Made Easy. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2809-2816. https://doi.org/10.1609/aaai.v33i01.33012809

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning