On Minimum ElementaryTriplet Bases for Independence Relations
[edit]
Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, PMLR 103:3237, 2019.
Abstract
A semigraphoid independence relation is a set of independence statements, called triplets, and is typically exponentially large in the number of variables involved. For concise representation of such a relation, a subset of its triplets is listed in a socalled basis; its other triplets are defined implicitly through a set of axioms. An elementarytriplet basis for this purpose consists of all elementary triplets of a relation. Such a basis however, may include redundant information. In this paper we provide two lower bounds on the size of an elementarytriplet basis in general and an upper bound on the size of a minimum elementarytriplet basis. We further specify the construction of an elementarytriplet basis of minimum size for restricted relations.
Related Material


