dc.contributor.author |
Link, Sebastian |
en |
dc.contributor.editor |
Ong, L |
en |
dc.contributor.editor |
de Queiroz, R |
en |
dc.coverage.spatial |
Buenos Aires, Argentina |
en |
dc.date.accessioned |
2012-12-04T02:47:33Z |
en |
dc.date.issued |
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 |
http://hdl.handle.net/2292/19702 |
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 http://www.sherpa.ac.uk/romeo/issn/0302-9743/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
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 |
pubs.place-of-publication |
Lecture Notes in Computer Science |
en |
pubs.start-date |
2012-09-03 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/RestrictedAccess |
en |
pubs.subtype |
Conference Paper |
en |
pubs.elements-id |
365834 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
pubs.record-created-at-source-date |
2012-11-29 |
en |