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.

On the expressive power of priorities in CHR

GABBRIELLI, MAURIZIO;MAURO, JACOPO;
2009

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, 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.
2009
Proceedings of PPDP 2009
267
276
M. Gabbrielli; J. Mauro; M.C. Meo
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/88474
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact