www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/10986

Title: Logical and algorithmic properties of stable conditional independence
Authors: Niepert, Mathias
Van Gucht, Dirk
GYSSENS, Marc
Issue Date: 2010
Publisher: ELSEVIER SCIENCE INC
Citation: INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 51(5). p. 531-543
Abstract: The logical and algorithmic properties of stable conditional independence (Cl) as an alternative structural representation of conditional independence information are investigated. We utilize recent results concerning a complete axiomatization of stable conditional independence relative to discrete probability measures to derive perfect model properties of stable conditional independence structures. We show that stable CI can be interpreted as a generalization of Markov networks and establish a connection between sets of stable CI statements and propositional formulas in conjunctive normal form. Consequently, we derive that the implication problem for stable CI is coNP-complete. Finally, we show that Boolean satisfiability (SAT) solvers can be employed to efficiently decide the implication problem and to compute concise, non-redundant representations of stable Cl, even for instances involving hundreds of random variables. (C) 2010 Elsevier Inc. All rights reserved.
Notes: [Niepert, Mathias] Univ Mannheim, Dept Comp Sci, KR & KM Res Grp, D-68159 Mannheim, Germany. [Van Gucht, Dirk] Indiana Univ, Dept Comp Sci, Bloomington, IN 47405 USA. [Gyssens, Marc] Hasselt Univ, Dept WNI, B-3590 Diepenbeek, Belgium. [Gyssens, Marc] Transnat Univ Limburg, B-3590 Diepenbeek, Belgium. mathias@informatik.uni-mannheim.de; vgucht@cs.indiana.edu; marc.gyssens@uhasselt.be
URI: http://hdl.handle.net/1942/10986
DOI: 10.1016/j.ijar.2010.01.011
ISI #: 000278692300006
ISSN: 0888-613X
Category: A1
Type: Journal Contribution
Validation: ecoom, 2011
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version356.26 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.