KR2023Proceedings of the 20th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 2-8, 2023.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-02-7

Sponsored by
Published by

Copyright © 2023 International Joint Conferences on Artificial Intelligence Organization

Foundations for Projecting Away the Irrelevant in ASP Programs

  1. Zeynep G. Saribatur(TU Wien)
  2. Stefan Woltran(TU Wien)


  1. Logic programming, answer set programming
  2. Computational aspects of knowledge representation


Simplification of logic programs under the answer-set semantics has been studied from the very beginning of the field. One natural simplification is the removal of atoms that are deemed irrelevant. While equivalence-preserving rewritings are well understood and incorporated in state-of-the-art systems, more careful rewritings in the realm of strong or uniform equivalence have received considerably less attention. This might be due to the fact that these equivalence notions rely on comparisons with respect to context programs that remain the same for both the original and the simplified program. In this work, we pursue the idea that the atoms considered irrelevant are disregarded accordingly in the context programs of the simplification, and propose novel equivalence notions for this purpose. We provide necessary and sufficient conditions for these kinds of simplifiability of programs, and show that such simplifications, if possible, can actually be achieved by just projecting the atoms from the programs themselves. We furthermore provide complexity results for the problems of deciding simplifiability and equivalence testing.