On the Expressive Power of Multiple Heads in CHR - Computer Science > Logic in Computer ScienceReportar como inadecuado




On the Expressive Power of Multiple Heads in CHR - Computer Science > Logic in Computer Science - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Constraint Handling Rules CHR is a committed-choice declarative languagewhich has been originally designed for writing constraint solvers and which isnowadays a general purpose language. CHR programs consist of multi-headedguarded rules which allow to rewrite constraints into simpler ones until asolved form is reached. Many empirical evidences suggest that multiple headsaugment the expressive power of the language, however no formal result in thisdirection has been proved, so far.In the first part of this paper we analyze the Turing completeness of CHRwith respect to the underneath constraint theory. We prove that if theconstraint theory is powerful enough then restricting to single head rules doesnot affect the Turing completeness of the language. On the other hand,differently from the case of the multi-headed language, the single head CHRlanguage is not Turing powerful when the underlying signature for theconstraint theory does not contain function symbols.In the second part we prove that, no matter which constraint theory isconsidered, under some reasonable assumptions it is not possible to encode theCHR language with multi-headed rules into a single headed language whilepreserving the semantics of the programs. We also show that, under somestronger assumptions, considering an increasing number of atoms in the head ofa rule augments the expressive power of the language.These results provide a formal proof for the claim that multiple headsaugment the expressive power of the CHR language.



Autor: Cinzia Di Giusto, Maurizio Gabbrielli, Maria Chiara Meo

Fuente: https://arxiv.org/







Documentos relacionados