Propositional reasoning about saturated conditional probabilistic independence

Show simple item record Link, Sebastian en
dc.contributor.editor Ong, L en
dc.contributor.editor de Queiroz, R en
dc.coverage.spatial Buenos Aires, Argentina en 2012-12-04T02:47:33Z en 2012-09 en
dc.identifier.citation Logic, Language, Information and Computation, Lecture Notes in Computer Science Volume 7456, 2012, pp 257-267 en
dc.identifier.isbn 978-3-642-32620-2 en
dc.identifier.issn 0302-9743 en
dc.identifier.uri en
dc.description.abstract Conditional independence provides an essential framework to deal with knowledge and uncertainty in Artificial Intelligence, and is fundamental in probability and multivariate statistics. Its associated implication problem is paramount for building Bayesian networks. Unfortunately, the problem does not enjoy a finite ground axiomatization and is already coNP-complete to decide for restricted subclasses. Saturated conditional independencies form an important subclass of conditional independencies whose implication problem is decidable in almost linear time. Geiger and Pearl have established a finite ground axiomatization for this class. We establish a new completeness proof for this axiomatization, utilizing a new sound inference rule. The proof introduces special probability models where two values have probability one half. Special probability models allow us to establish a semantic proof for the equivalence between the implication of saturated conditional independencies and formulae in a Boolean propositional fragment. The equivalence extends the duality between the propositional fragment and multivalued dependencies in relational databases to a trinity involving saturated conditional independencies. en
dc.publisher Springer en
dc.relation.ispartof Logic, Language, Information and Computation en
dc.relation.ispartofseries 19th International Workshop on Logic, Language, Information and Computation (WoLLIC 2012) en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from en
dc.rights.uri en
dc.title Propositional reasoning about saturated conditional probabilistic independence en
dc.type Conference Item en
dc.identifier.doi 10.1007/978-3-642-32621-9_19 en
pubs.begin-page 257 en
pubs.volume 7456 en
dc.rights.holder Copyright: Springer-Verlag Berlin Heidelberg 2012 en
pubs.end-page 267 en
pubs.finish-date 2012-09-06 en Lecture Notes in Computer Science en
pubs.start-date 2012-09-03 en
dc.rights.accessrights en
pubs.subtype Conference Paper en
pubs.elements-id 365834 en Science en School of Computer Science en
pubs.record-created-at-source-date 2012-11-29 en

Files in this item

There are no files associated with this item.

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace