A. Paz, R. Y. Geva and M. Studeny:
Representation of irrelevance relations by annotated graphs.
Fundamenta Informaticae 42 (2000), pp. 149-199.
- 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).
- AMS classification 68T30
- irrelevance relation
- (regular) annotated graph
- membership testing algorithm
- annotation algorithm
pdf copy (converted postscript version) (419kB) is available.