On the expressive power of priorities in CHR

Constraint Handling Rules (CHR) is a committed-choice declarative language which has been originally designed for writing constraint solvers and which is nowadays a general purpose language. Recently the language has been extended by introducing user-definable (static or dynamic) rule priorities. The resulting language, called CHRrp, allows a better control over execution while retaining a declarative and flexible style of programming. In this paper we study the expressive power of this language from the view point of the concurrency theory. We first show that dynamic priorities do not augment the expressive power by providing an encoding of dynamic priorities into static ones. Then we show that, when considering the theoretical operational semantics, CHRrp is strictly more expressive than CHR. This result is obtained by using a problem similar to the leader-election to show that, under some conditions, there exists no encoding of CHRrp into CHR. We also show, by using a similar technique, that the CHR language with the, so called, refined semantics is more expressive power than CHR with theoretical semantics and we extend some previous results showing that CHR can not be encoded into Prolog.