The expressive power of CHR with priorities - Archive ouverte HAL Access content directly
Journal Articles Information and Computation Year : 2013

The expressive power of CHR with priorities

(1, 2) , (2, 3) , (4)
1
2
3
4

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.

Dates and versions

hal-00909295 , version 1 (26-11-2013)

Identifiers

Cite

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

Collections

INRIA INRIA2
128 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More