Pavel Naumov and Brittany Nicholls

The paper investigates properties of the conditional independence relation between pieces of information. This relation is also known in the database theory as embedded multi-valued dependency. In 1980, Parker and Parsaye-Ghomi established that the properties of this relation can not be described by a finite system of inference rules. In 1995, Herrmann proved that the propositional theory of this relation is undecidable. The main result of this paper is a complete recursively enumerable axiomatization of this theory. [pdf]