ECAI'08 Workshop
on
Inference methods based on Graphical Structures of Knowledge

The use of graphical structures to improve the efficiency of inference and search has been intensively developed in the last few years. In particular, local computation on join trees (including variable/bucket elimination) has proved to be a very general method of computation in reasoning formalisms, and for knowledge compilation. It has been shown to be applicable, in particular, to probability, possibility theory and other uncertainty calculi, relational databases, constraints including finite constraints, soft constraints, linear constraints and inequalities, and a wide range of logics, including propositional and first-order classical logics and modal logics.

Recently it has also be shown that another family of representations can be applied for many of the same problems; this family includes NNFs, tree-automata, AND/OR graph representations and decision diagrams. In addition, incomplete graph-based propagation algorithms have been used in the solving of hard and soft constraints. The focus of this workshop will be on these graphical approaches, and their use in enabling structural properties of problems to be exploited for inference or search, in particular, for reasoning with soft constraints and preferences, decision making and uncertain inference.

The proposed workshop follows on from the ECAI-04 workshop on Local Computation for Logics and Uncertainty and the ECAI-06 workshop on Inference methods based on Graphical Structures of Knowledge.

Program

• 9.15 : Welcome
• 9.20 : Branch-and-Bound for Soft Constraints Based on Partially Ordered Degrees of Preference, Nic Wilson and Hélène Fargier
(download pdf)
• 10.00 : coffee break
• 10.30 : On Automata, MDDs and BDDs in Constraint Satisfaction, Tarik Hadzic, Esben Rune Hansen and Barry O'Sullivan
(download pdf)
• 11.10 : Two Encodings of DNNF Theories, Jean Christoph Jung and Pedro Barahona and George Katsirelos and Toby Walsh
(download pdf)
• 11.50 : Advancing AND/OR Search for Optimization Using Diverse Principles, Radu Marinescu and Rina Dechter
(download pdf)
• 12.30 : lunch break
• 14.00 : Invited talk by Pierre Marquis : On Propositional Independence
• 14.50 : Local Computation Schemes with Partially Ordered Preferences, Hélène Fargier and Nic Wilson
(download pdf)
• 15.30 : coffee break
• 16.00 : Uniform Interpolation By Resolution In Modal Logic, Andreas Herzig and Jérôme Mengin
(download pdf)
• 16.40 : end

Please note that workshop attendees are required to register also for the main conference.
See the ECAI 2008 registration page.

ORGANIZING/PROGRAM COMMITTEE

Rina Dechter
School of Information and Computer Science, University of California, Irvine, USA

Hélène Fargier
Institut de Recherche en Informatique de Toulouse, Université Paul Sabatier, Toulouse, France.

Jürg Kohlas
Department of Informatics, University of Fribourg, Switzerland.

Jérôme Mengin
Institut de Recherche en Informatique de Toulouse, Université Paul Sabatier, Toulouse, France.

Gérard Verfaillie
ONERA, Toulouse, France.

Nic Wilson
Cork Constraint Computation Centre, University College Cork, Ireland.