Conditional independence in propositional logic

Independence—the study of what is relevant to a given problem of reasoning—is an important AI topic. In this paper, we investigate several notions of conditional independence in propositional logic: Darwiche and Pearl's conditional independence, and some more restricted forms of it. Many characterizations and properties of these independence relations are provided. We show them related to many other notions of independence pointed out so far in the literature (mainly formula-variable independence, irrelevance and novelty under various forms, separability, interactivity). We identify the computational complexity of conditional independence and of all these related independence relations.

Authors

• Jérôme Lang CNRS, Université Paris Dauphine, PSL
• Paolo Liberatore Università di Roma "La Sapienza"
• Pierre Marquis Univ. Artois, CNRS, CRIL, Lens, France Institut Universitaire de France

Keywords

• Conditional independence
• Relevance
• Novelty
• Separability