Course at the CHR summer school 2013: Abduction and language processing with CHR

Henning Christiansen, Roskilde University, Denmark

A course which is part of the CHR Summer School, Berlin, Germany, July 2013.

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 system 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.

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 a recent adaptation of CHR with persistent constraint stores, shared between different software agent. This system is intended for the knowledge intensive components in interactive installation, but seems also to be relevant for a wider class of applications.


Find pdf version here (Keynote version for Mac available from the author.) Please notice copyright; write to author if any doubt.

Software and sample programs

Motivating examples, abduction in CHR and Prolog: happy1, happy2, happy3.

Diagnosis with CHR and Prolog: diagnosisPeriodic, diagnosisConsistent.

Planning with CHR and Prolog: planning.

Language analysis with CHR and DCG: simpleDCG, discourse1, discourse2.
Find also more examples that runs under the Hyprolog system.

Language analysis with CHR Grammars: Find CHRG system and lots of sample grammars at CHRG website.


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

Christiansen: An adaptation of Constraint Handling Rules for interactive and intelligent installations. CHR Workshop 2012.

Christiansen: An exposition of abductive reasoning through logic programming with constraints. SLS 2012, the Scandinavian Logic Symposium, 2012.

van de Camp, Christiansen. Resolving relative time expressions in Dutch text with Constraint Handling Rules. CSLP 2012. To appear in LNCS, 2013.

Christiansen, Li: Approaching the Chinese word segmentation problem with CHR grammars. CSLP 2011. To appear in a book 2013 or -14. Christiansen, Saleh: Modeling dependent events with CHRiSM for probabilistic abduction. CHR Workshop 2011.

Christiansen, Have, Tveitane: From use cases to UML class diagrams using logic grammars and constraints. RANLP 2007.

Christiansen, Have, Tveitane: Reasoning about use cases using logic grammars and constraints. CSLP 2007.

You may find full references and more links at and

Last modification July 11, 2013