Towards classification of semigraphoids
| Autor: | František Matúš |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
Discrete mathematics
Lemma (mathematics) Closure Probabilistic representation Linear space Structure (category theory) Generator Disjoint sets Linear representation Semigraphoid Theoretical Computer Science Combinatorics Closure (mathematics) Simple (abstract algebra) Conditional independence Discrete Mathematics and Combinatorics Canonical form Polymatroid Finite set Mathematics |
| Zdroj: | Discrete Mathematics. 277:115-145 |
| ISSN: | 0012-365X |
| Popis: | Semigraphoids are special sets of triples (I,J,K), I,J,K disjoint subsets of a finite set, that mimic conditional independences. New constructions on semigraphoids are introduced, the most crucial being factors and expansions. They are aimed at study of new classes of semigraphoids, that are constructed from semigraphoids of a trivial structure, e.g. from uniform semigraphoids, and at bringing each semigraphoid to a canonical form. Canonical semigraphoids are defined and each semigraphoid is constructed from a canonical one by means of a pure minor and an expansion. Semigraphoid closure and generators are investigated. The case of two generators is analysed in detail. Invariants for semigraphoids based on relations among generators are introduced and the corresponding classes of semigraphoids are related to classes built from uniform semigraphoids. Representability of semigraphoids by linear spaces and random variables is reexamined. The semigraphoids with at most two generators are proved to be linear and hence, by a simple lemma, probabilistic. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect