Talks and Poster Presentations (with Proceedings-Entry):
W. Faber, M. Morak, S. Woltran:
"Strong Equivalence for Epistemic Logic Programs Made Easy";
Talk: AAAI 2019 - 33rd Conference on Artificial Intelligence,
Honolulu, Hawaii;
2019-01-27
- 2019-02-01; in: "The Thirty-Third {AAAI} Conference on Artificial Intelligence, {AAAI} 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, {IAAI} 2019, The Ninth {AAAI} Symposium on Educational Advances in Artificial Intelligence, {EAAI} 2019",
AAAI Press,
(2019),
ISBN: 978-1-57735-809-1;
2809
- 2816.
English 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.
Keywords:
Strong Equivalence for Epistemic Logic Programs Made Easy, ELPs
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1609/aaai.v33i01.33012809
Related Projects:
Project Head Stefan Woltran:
START
Created from the Publication Database of the Vienna University of Technology.