An Algebraic Notion of Conditional Independence, and Its Application to Knowledge Representation (full version)
This provides a foundational tool for knowledge representation, allowing efficient reasoning across various logics with fixpoint semantics, though it builds incrementally on existing conditional independence concepts.
The paper tackles the problem of defining conditional independence in a language-independent algebraic framework using approximation fixpoint theory, enabling global reasoning to be reduced to parallel local reasoning and achieving fixed-parameter tractability results.
Conditional independence is a crucial concept supporting adequate modelling and efficient reasoning in probabilistics. In knowledge representation, the idea of conditional independence has also been introduced for specific formalisms, such as propositional logic and belief revision. In this paper, the notion of conditional independence is studied in the algebraic framework of approximation fixpoint theory. This gives a language-independent account of conditional independence that can be straightforwardly applied to any logic with fixpoint semantics. It is shown how this notion allows to reduce global reasoning to parallel instances of local reasoning, leading to fixed-parameter tractability results. Furthermore, relations to existing notions of conditional independence are discussed and the framework is applied to normal logic programming.