Abduction and language processing with CHR

Henning Christiansen, Roskilde University, Denmark

A course which is part of the CHR Summer School, Leuven, Belgium, Aug 30-Sep 3, 2010.

Abduction refers to the sort reasoning that infers facts by means of which a given observation can be explained. This can be understood as reasoning backwards from an observed effect to its possible cause, e.g., from symptoms to diagnosis. Abduction is often accompanied by so-called integrity constraints that limit the inferred facts or causes to be what is believed to conform with some possible world.

CHR allows an elegant encoding of abduction, by mapping abducible facts into CHR constraints and integrity constraints into CHR rules. Combining this with Prolog as a general knowledge representation yields an easy-to-use and powerful environment for abductive reasoning. When, furthermore, this is combined with Prolog's grammar notation, DCGs, we obtain a system abductive language interpretation. These techniques can be used directly in CHR+Prolog or via the HYPROLOG system which adds utilities and a thin layer of syntactic sugar on top.

CHR Grammars represent another system in which CHR rules are applied for bottom-up analysis, which can also be combined with abduction in CHR as described.

Finally, we show how probabilistic abduction can be expressed and implemented in a CHR program which searches for the best, i.e., the most probable, explanation of the observation.

A basic background in logic programming will be helpful for this course, but is not strictly necessary. With or without a background in linguistics, students can benefit from the parts on language analysis.

Example programs

Click to get to directory


Write to the author for a printable version with extended reference list.


Abdennadher+Christiansen: An Experimental CLP Platform for Integrity Constraints and Abduction. Proc. FQAS2000, pp. 141--152, Advances in Soft Computing series, Springer, 2000.
– First reference to abduction in CHR. pdf

Christiansen+Dahl: HYPROLOG: A New Logic Programming Language with Assumptions and Abduction, Proc. International Conference on Logic Programming, ICLP'05, pp. 159-173, 2005. Lecture Notes in Computer Science 3668.

Christiansen: CHR grammars. International Journal on Theory and Practice of Logic Programming, vol. 4+5, special issue on Constraint Handling Rules, pp. 467-501, 2005.

Christiansen: Implementing Probabilistic Abductive Logic Programming with Constraint Handling Rules, Constraint Handling Rules, Current Research Topics. T. Schrijvers, T. Frühwirth (eds.). Lecture Notes in Artificial Intelligence 5388, Springer 2008. pp. 85-118.

Christiansen. Executable specifications for hypothesis-based reasoning with Prolog and Constraint Handling Rules, Journal of Applied Logic, vol 7, 2009. pp. 341-362.

Christiansen: Artificial Intelligence and Intelligent Systems: Logic programming as a framework for Knowledge Representation and Artificial Intelligence. Roskilde University, 2006.
– A course note with pedagogical introductions to Prolog and CHR with applications for abduction; many examples. pdf


HYPROLOG: Source code, User's guide, examples.

CHR Grammars: Source code, User's guide, examples.
NB: Only available for SICStus 3; a new version for SICStus 4 and SWI will appear soon.

Last modification September 1, 2010