Expressive power of Constraint Handling Rules extensions and fragments

Abstract

Constraints can be used in concurrency theory to increase the conciseness and the expressive power of concurrent languages from a pragmatic point of view. In this work we study the expressive power of concurrent language, namely Constraint Handling Rules, that supports constraints as a primitive construct. We show what features of this language make it Turing powerful and what happens to its expressive power if priorities are introduced.