On the Expressive Power of Multiple Heads in CHR

Cinzia Di Giusto 1 Maurizio Gabbrielli 2, 3 Maria Chiara Meo 4
1 SARDES - System architecture for reflective distributed computing environments
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : Constraint Handling Rules (CHR) is a committed-choice declarative language that has been originally designed for writing constraint solvers and is nowadays a general purpose language. CHR programs consist of multiheaded guarded rules which allow to rewrite constraints into simpler ones until a solved form is reached. Many empirical evidences suggest that multiple heads augment the expressive power of the language, however no formal result in this direction has been proved, so far. In the first part of this article we analyze the Turing completeness of CHR with respect to the underlying constraint theory. We prove that if the constraint theory is powerful enough then restricting to single head rules does not affect the Turing completeness of the language. On the other hand, differently from the case of the multiheaded language, the single head CHR language is not Turing powerful when the underlying signature (for the constraint theory) does not contain function symbols. In the second part we prove that, no matter which constraint theory is considered, under some reasonable assumptions it is not possible to encode the CHR language (with multi-headed rules) into a single headed language while preserving the semantics of the programs. We also show that, under some stronger assumptions, considering an increasing number of atoms in the head of a rule augments the expressive power of the language. These results provide a formal proof for the claim that multiple heads augment the expressive power of the CHR language.
Type de document :
Article dans une revue
ACM Transactions on Computational Logic, Association for Computing Machinery, 2012, 13 (1), 〈10.1145/2071368.2071374〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00909390
Contributeur : Davide Sangiogi <>
Soumis le : mardi 26 novembre 2013 - 11:08:36
Dernière modification le : mercredi 11 avril 2018 - 01:57:42

Lien texte intégral

Identifiants

Collections

Citation

Cinzia Di Giusto, Maurizio Gabbrielli, Maria Chiara Meo. On the Expressive Power of Multiple Heads in CHR. ACM Transactions on Computational Logic, Association for Computing Machinery, 2012, 13 (1), 〈10.1145/2071368.2071374〉. 〈hal-00909390〉

Partager

Métriques

Consultations de la notice

214