Expressiveness of Multiple Heads in CHR

C. Di Giusto, M. Gabbrielli and M.C.Meo
In SOFSEM 2009, volume 5404 of LNCS pages 205-216, 2009.
Constraint Handling Rules (CHR) is a general purpose, committed- choice declarative language which, differently from other similar languages, uses multi-headed (guarded) rules. In this paper we prove that multiple heads augment the expressive power of the language. In fact, we first show that restricting to single head rules affects the Turing completeness of CHR, provided that the underlying signature (for the constraint theory) does not contain function symbols. Next we show that, also when considering generic constraint theories, under some rather reasonable assumptions it is not possible to encode CHR (with multi-headed rules) into a single-headed CHR language while preserving the semantics of programs. As a corollary we obtain that, under these assumptions, CHR can be encoded neither in (constraint) logic programming nor in pure Prolog.