On Forgetting in Tractable Propositional Fragments

2015/02/10 by Yisong Wang, Wang, Yisong
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Rough Sets and Fuzzy Logic #cs.AI

paper · pdf · doi:10.48550/arxiv.1502.02799

27 pages

arxiv created 2015/02/10 · openalex publication_date 2015/02/10 · arxiv updated 2015/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Four algorithms for propositional forgetting
• One head is better than two: a polynomial restriction for propositional definite Horn forgetting
• The ghosts of forgotten things: A study on size after forgetting
• An Approach to Forgetting in Disjunctive Logic Programs that Preserves Strong Equivalence
• Common equivalence and size after forgetting