Research map / Learning theory and algorithms / Combinatorial and search optimization

An Algebraic Notion of Conditional Independence, and Its Application to Knowledge Representation

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Logic and answer set programming theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Defines an algebraic, operator-based notion of conditional independence for lattices and approximation operators, derives modular fixpoint and FPT results, and applies it to normal logic programs.

Problem

Conditional independence is well studied in probability and for specific KR formalisms (propositional logic, belief revision, conditional logics) but lacks a language-independent operator-based account that enables modular reasoning over fixpoint semantics.

Approach

Define conditional independence of sub-lattices w.r.t. an operator on a product lattice, so the operator decomposes into two component operators over pivot-plus-one-side sub-lattices; lift this to approximation operators and stable/well-founded fixpoints, and organize decompositions into conditional independence trees whose size parametrizes FPT algorithms.

Key results

• Shows that fixpoints (Kripke-Kleene, stable, well-founded) of an approximation operator with conditional independence decompose into fixpoints of component operators over sub-lattices.
• Proves the least fixpoint and well-founded fixpoint can be computed in FPT time parameterized by CIT-size, under NP-oracle assumptions for the operator.
• Shows a syntactic sufficient criterion (graph separation plus stratification) for conditional independence in normal logic programs.

Surprising findings

• Symmetry holds but decomposition and weak union do not hold for the proposed notion of conditional independence.
• Naive graph separation in the dependency graph is not sufficient for conditional independence in normal logic programs.

Limitations

• No experimental evaluation of computational gains.
• Complexity of computing CIT-partition-size and detecting conditional independence is not addressed in general.
• Application is restricted to normal logic programs; other formalisms are left for future work.

Experimental setup

Builds on: approximation fixpoint theory stratification in AFT Darwiche's logical conditional independence

Closest papers by meaning

• An Alternative Theory of Stable Revision for Nondeterministic Approximation Fixpoint Theory and the Relationships (AAAI 2025 · similarity 0.87)
• Using Conditional Independence for Belief Revision (AAAI 2022 · similarity 0.87)
• Contextual Conditional Reasoning (AAAI 2021 · similarity 0.86)
• Model Checking Probabilistic Knowledge: A PSPACE Case (AAAI 2016 · similarity 0.86)
• Decomposing Constraint Networks for Calculating c-Representations (AAAI 2024 · similarity 0.84)
• From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy (ICLR 2025 · similarity 0.84)