On Forgetting in Tractable Propositional Fragments
This work addresses a foundational gap in AI for knowledge representation, providing computational tools for forgetting in tractable propositional fragments, though it appears incremental as it builds on existing logical frameworks.
The paper tackles the problem of forgetting in propositional logic by developing a resolution-based algorithm for the CNF fragment and analyzing complexity results across various tractable fragments, such as Horn and Krom, to address the lack of general computational methods in this area.
Distilling from a knowledge base only the part that is relevant to a subset of alphabet, which is recognized as forgetting, has attracted extensive interests in AI community. In standard propositional logic, a general algorithm of forgetting and its computation-oriented investigation in various fragments whose satisfiability are tractable are still lacking. The paper aims at filling the gap. After exploring some basic properties of forgetting in propositional logic, we present a resolution-based algorithm of forgetting for CNF fragment, and some complexity results about forgetting in Horn, renamable Horn, q-Horn, Krom, DNF and CNF fragments of propositional logic.