In this paper we describe an algorithm for computing the closure with respect to graphoid properties of a set of independencies under graphoid properties. Since the computation of the complete closure is infeasible, we propose to use a procedure, called FC1, which is based on a unique inference rule and on the elimination of redundant independencies. FC1 is able to compute a reduced form of the closure, called fast closure, which is equivalent to the complete closure, but whose size is much smaller. Some experimental tests have been performed with an implementation of the procedure in order to show the computational behaviour of the algorithm. We have also compared the computational cost and the size of the fast closure with the corresponding data for the complete closure.
Keywords. Conditional independence models, Graphoid properties, Inferential rules
Paper Download
The paper is availabe in the following formats:
Plenary talk : Press here to get the file of the presentation.
Poster : Press here to get the file of the poster.
Authors addresses:
Marco Baioletti
Dipartimento di Matematica e Informatica
Via Vanvitelli
06125 Perugia
Italy
Giuseppe Busanello
via A. Scarpa 16,
I-00161 Rome,
Italy
Barbara Vantaggi
Dipartimento Metodi e Modelli Matematici
Universita' La Sapienza
via Scarpa n. 16 Roma,
00161, Italy
E-mail addresses:
| Marco Baioletti | baioletti@dipmat.unipg.it |
| Giuseppe Busanello | busanello@dmmm.uniroma1.it |
| Barbara Vantaggi | vantaggi@dmmm.uniroma1.it |