Studeny.a19

A. Paz, R. Y. Geva, M. Studeny: Representation of irrelevance relations by annotated graphs. Fundamenta Informaticae 42 (2000), pp. 149-199.

Abstract
Irrelevance relations are lists of irrelevance statements of the form: given the value of Z is known, the 'values' of Y can add no further information about the value of X. Undirected graphs, directed acyclic graphs and chain graphs were used and investigated as schemes for the purpose of representing irrelevance relations. In this paper annotated graphs are defined and suggested as a new model for representation of irrelevance relations. Informally, an annotated graph is an undirected graph whose edges are annotated by nonemty sets of remaining nodes. A certain class of regular annotated graph is introduced and an algorithm for testing represented irrelevance statements is given. It is shown that the irrelevance relation induced by a regular annotated graph is always a graphoid. The new model is a proper generalization of the former models: any irrelevance relation that can be represented by either one of the previous models can be represented by a regular annotated graph, and there are relations that can be represented by a regular annotated graph but cannot be represented by either one of former models. In fact, it is shown that given a sequence of embedded undirected graphs, the graphoid closure of the union of their induced irrelevance relations can be represented by a regular annotated graph (an algorithm producing such an annotated graph is described).

Keywords: irrelevance relation; graphoid; (regular) annotated graph; membership testing algorithm; annotation algorithm