On Syntactic Forgetting Under Uniform Equivalence

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)


Forgetting in Answer Set Programming (ASP) aims at reducing the language of a logic program without affecting the consequences over the remaining language. It has recently gained interest in the context of modular ASP where it allows simplifying a program of a module, making it more declarative, by omitting auxiliary atoms or hiding certain atoms/parts of the program not to be disclosed. Unlike for arbitrary programs, it has been shown that forgetting for modular ASP can always be applied, for input, output and hidden atoms, and preserve all dependencies over the remaining language (in line with uniform equivalence). However, the definition of the result is based solely on a semantic characterization in terms of HT-models. Thus, computing an actual result is a complicated process and the result commonly bears no resemblance to the original program, i.e., we are lacking a corresponding syntactic operator. In this paper, we show that there is no forgetting operator that preserves uniform equivalence (modulo the forgotten atoms) between the given program and its forgetting result by only manipulating the rules of the original program that contain the atoms to be forgotten. We then present a forgetting operator that preserves uniform equivalence and is syntactic whenever this is suitable. We also introduce a special class of programs, where syntactic forgetting is always possible, and as a complementary result, establish it as the largest known class where forgetting while preserving all dependencies is always possible.

Original languageEnglish
Title of host publicationLogics in Artificial Intelligence - 17th European Conference, JELIA 2021, Proceedings
EditorsWolfgang Faber, Gerhard Friedrich, Martin Gebser, Michael Morak
Place of PublicationCham
Number of pages16
ISBN (Electronic)978-3-030-75775-5
ISBN (Print)978-3-030-75774-8
Publication statusPublished - 2021
Event17th European Conference on Logics in Artificial Intelligence, JELIA 2021 - Virtual, Online
Duration: 17 May 202120 May 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12678 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th European Conference on Logics in Artificial Intelligence, JELIA 2021
CityVirtual, Online


  • Answer Set Programming
  • Forgetting
  • Uniform equivalence


Dive into the research topics of 'On Syntactic Forgetting Under Uniform Equivalence'. Together they form a unique fingerprint.

Cite this