On Forgetting in Tractable Propositional Fragments
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Belief merging within fragments of propositional logic
Recently, belief change within the framework of fragments of propositional logic has gained increasing attention. Previous works focused on belief contraction and belief revision on the Horn fragment. However, the proble…
A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monot…
Abductive forgetting
Abductive forgetting is removing variables from a logical formula while maintaining its abductive explanations. It is defined in either of two ways, depending on its intended application. Both differ from the usual forge…
Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework
Logic-based argumentation is a well-established formalism modelling nonmonotonic reasoning. It has been playing a major role in AI for decades, now. Informally, a set of formulas is the support for a given claim if it is…
The ghosts of forgotten things: A study on size after forgetting
Forgetting is removing variables from a logical formula while preserving the constraints on the other variables. In spite of being a form of reduction, it does not always decrease the size of the formula and may sometime…