On Minimum Elementary-Triplet Bases for Independence Relations
Abstract
A semi-graphoid 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 so-called basis; its other triplets are defined implicitly through a set of axioms. An elementary-triplet 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 elementary-triplet basis in general and an upper bound on the size of a minimum elementary-triplet basis. We further specify the construction of an elementary-triplet basis of minimum size for restricted relations.
Cite
Text
Bolt and Gaag. "On Minimum Elementary-Triplet Bases for Independence Relations." Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, 2019.Markdown
[Bolt and Gaag. "On Minimum Elementary-Triplet Bases for Independence Relations." Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, 2019.](https://mlanthology.org/isipta/2019/bolt2019isipta-minimum/)BibTeX
@inproceedings{bolt2019isipta-minimum,
title = {{On Minimum Elementary-Triplet Bases for Independence Relations}},
author = {Bolt, Janneke and Gaag, Linda C.},
booktitle = {Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications},
year = {2019},
pages = {32-37},
volume = {103},
url = {https://mlanthology.org/isipta/2019/bolt2019isipta-minimum/}
}