Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Davide Sangiogi Connect in order to contact the contributor
Submitted on : Tuesday, November 26, 2013 - 10:44:57 AM
Last modification on : Friday, October 30, 2020 - 12:04:02 PM

Links full text




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⟩



Les métriques sont temporairement indisponibles