Annals of Pure and Applied Logic 170 (9):975-992 (2019)

Jouko A Vaananen
University of Helsinki
Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of d-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements are modeled by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2019.04.004
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,436
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Dependence and Independence.Erich Grädel & Jouko Väänänen - 2013 - Studia Logica 101 (2):399-410.
Axiomatizing First-Order Consequences in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2013 - Annals of Pure and Applied Logic 164 (11):1101-1117.
Axiomatizing First-Order Consequences in Independence Logic.Miika Hannula - 2015 - Annals of Pure and Applied Logic 166 (1):61-91.
Independence Logic and Abstract Independence Relations.Gianluca Paolini - 2015 - Mathematical Logic Quarterly 61 (3):202-216.

View all 9 references / Add more references

Citations of this work BETA

On Elementary Logics for Quantitative Dependencies.Miika Hannula, Minna Hirvonen & Juha Kontinen - forthcoming - Annals of Pure and Applied Logic:103104.

Add more citations

Similar books and articles

On Definability in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2009 - Journal of Logic, Language and Information 18 (3):317-332.
Logical Independence in Quantum Logic.Miklós Rédei - 1995 - Foundations of Physics 25 (3):411-422.
Frege's New Science.G. Aldo Antonelli & Robert C. May - 2000 - Notre Dame Journal of Formal Logic 41 (3):242-270.
Elementary Prepositions, Independence, and Pictures.Rod Bertolet - 1991 - Journal of Philosophical Research 16:53-61.
Elementary Prepositions, Independence, and Pictures.Rod Bertolet - 1991 - Journal of Philosophical Research 16:53-61.
Independence in Finitary Abstract Elementary Classes.Tapani Hyttinen & Meeri Kesälä - 2006 - Annals of Pure and Applied Logic 143 (1-3):103-138.
Factoring Out the Impossibility of Logical Aggregation.Philippe Mongin - 2008 - Journal of Economic Theory 141:p. 100-113.


Added to PP index

Total views
14 ( #735,344 of 2,519,857 )

Recent downloads (6 months)
1 ( #406,012 of 2,519,857 )

How can I increase my downloads?


My notes