The expressive power of CHR with priorities

Abstract : 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 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. We first show that, in the presence of priorities, differently from the case of standard CHR, considering more than two atoms in the heads of rules does not augment the expressive power of the language. Next we show that also dynamic priorities do not augment the expressive power w.r.t. static priorities. These results are proved by providing explicitly a translation of one language into another one, which preserves a reference semantics. Finally we show that CHR with priorities is strictly more expressive than standard CHR (under the theoretical operational semantics). This result is obtained by adapting to the CHR case a notion of language encoding which allows to compare Turing powerful languages.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2013, 228-229, pp.62-82. 〈10.1016/j.ic.2013.05.001〉
Liste complète des métadonnées
Contributeur : Davide Sangiogi <>
Soumis le : mardi 26 novembre 2013 - 10:44:57
Dernière modification le : samedi 27 janvier 2018 - 01:32:19

Lien texte intégral




Maurizio Gabbrielli, Jacopo Mauro, Maria Chiara Meo. The expressive power of CHR with priorities. Information and Computation, Elsevier, 2013, 228-229, pp.62-82. 〈10.1016/j.ic.2013.05.001〉. 〈hal-00909295〉



Consultations de la notice