Document Server@UHasselt >
Research >
Research publications >

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

Title: On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements
Authors: GYSSENS, Marc
Niepert, Mathias
Van Gucht, Dirk
Issue Date: 2014
Citation: INFORMATION PROCESSING LETTERS, 114 (11), p. 628-633
Abstract: Conditional independence (CI) statements occur in several areas of computer science and artificial intelligence, e.g., as embedded multivalued dependencies in database theory, disjunctive association rules in data mining, and probabilistic CI statements in probability theory. Although, syntactically, such constraints can always be represented in the form I(A, B vertical bar C), with A, B, and C subsets of some universe S, their semantics is very dependent on their interpretation, and, therefore, inference rules valid under one interpretation need not be valid under another. However, all aforementioned interpretations obey the so-called semigraphoid axioms. In this paper, we consider the restricted case of deriving arbitrary CI statements from so-called saturated ones, i.e., which involve all elements of S. Our main result is a necessary and sufficient condition under which the semigraphoid axioms are also complete for such derivations. Finally, we apply these results to the examples mentioned above to show that, for these semantics, the semigraphoid axioms are both sound and complete for the derivation of arbitrary CI statements from saturated ones. (C) 2014 Elsevier B.V. All rights reserved.
Notes: [Gyssens, Marc] Hasselt Univ, B-3500 Hasselt, Belgium. [Gyssens, Marc] Transnat Univ Limburg, Fac Sci, B-3500 Hasselt, Belgium. [Niepert, Mathias] Univ Washington, Paul G Allen Ctr, Dept Comp Sci & Engn, Seattle, WA 98195 USA. [Van Gucht, Dirk] Indiana Univ, Div Comp Sci, Bloomington, IN 47405 USA. marc.gyssens@uhasselt.be; mniepert@cs.washington.edu; vgucht@cs.indiana.edu
URI: http://hdl.handle.net/1942/17775
DOI: 10.1016/j.ipl.2014.05.010
ISI #: 000340324300008
ISSN: 0020-0190
Category: A1
Type: Journal Contribution
Validation: ecoom, 2015
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version360.67 kBAdobe PDF
N/A297.92 kBAdobe PDF

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