Expressiveness of Multiple Heads in CHR

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 Tur- ing completeness of CHR, provided that the underlying signature (for the constra- int theory) does not contain function symbols. Next we show that, also when con- sidering 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.