On the expressive power of priorities in CHR

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the expressive power of priorities in CHR

Full text

Pdf (455 KB)

Source

International Conference on Principles and Practice of Declarative Programming archive
Proceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming table of contents

Coimbra, Portugal

SESSION: Constraints table of contents

Pages 267-276

Year of Publication: 2009

ISBN:978-1-60558-568-0

Authors

Maurizio Gabbrielli	University of Bologna, Bologna, Italy
Jacopo Mauro	University of Bologna, Bologna, Italy
Maria Chiara Meo	University of Chieti, Pescara, Italy

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 2, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1599410.1599443 What is a DOI?

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 CHR^rp, 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, CHR^rp 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 CHR^rp 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Frank S. de Boer and Catuscia Palamidessi. Embedding as a tool for language comparison. Information and Computation, 108 (1): 128--157, 1994.
	2	Leslie De Koninck, Tom Schrijvers, and Bart Demoen. User-definable rule priorities for chr. In Michael Leuschel and Andreas Podelski, editors, PPDP, pages 25--36. ACM, 2007. ISBN 978--1--59593--769--8.
	3	Cinzia Di Giusto, Maurizio Gabbrielli, and Maria Chiara Meo. Expressiveness of multiple heads in chr. In Mogens Nielsen, Antonín Kucera, Peter Bro Miltersen, Catuscia Palamidessi, Petr Tuma, and Frank D. Valencia, editors, SOFSEM, volume 5404 of Lecture Notes in Computer Science, pages 205--216. Springer, 2009. ISBN 978-3-540-95890-1.
	4	Gregory J. Duck, Peter J. Stuckey, Maria J. García de la Banda, and Christian Holzbaur. The refined operational semantics of constraint handling rules. In Bart Demoen and Vladimir Lifschitz, editors, ICLP, volume 3132 of phLecture Notes in Computer Science, pages 90--104. Springer, 2004. ISBN 3-540-22671-0.
	5	T. Frühwirth. As time goes by: Automatic complexity analysis of simplification rules. In KR 02, 2002.
	6	Thom Frühwirth. Introducing simplification rules. Technical report, 1991.
	7	Thom W. Frühwirth. Theory and practice of constraint handling rules. J. Log. Program., 37 (1-3): 95--138, 1998a.
	8	Thom W. Frühwirth. As time goes by II: More automatic complexity analysis of concurrent rule programs. Electr. Notes Theor. Comput. Sci., 59 (3), 2001.
	9	Thom W. Frühwirth. Theory and practice of constraint handling rules. J. Log. Program., 37 (1-3): 95--138, 1998b.
	10	Catuscia Palamidessi. Comparing the expressive power of the synchronous and asynchronous pi-calculi. Mathematical. Structures in Comp. Sci., 13 (5): 685--719, 2003. ISSN 0960-1295.
	11	Ehud Y. Shapiro. The family of concurrent logic programming languages. ACM Comput. Surv., 21 (3): 413--510, 1989.
	12	Jon Sneyers. Turing-complete subclasses of chr. In Maria Garcia de la Banda and Enrico Pontelli, editors, ICLP, volume 5366 of Lecture Notes in Computer Science, pages 759--763. Springer, 2008. ISBN 978-3-540-89981-5.
	13	Jon Sneyers, Tom Schrijvers, and Bart Demoen. The computational power and complexity of constraint handling rules. ACM Trans. Program. Lang. Syst., 31 (2), 2009.
	14	Frits W. Vaandrager. Expressive results for process algebras. In Proceedings of the REX Workshop on Sematics: Foundations and Applications, pages 609--638, London, UK, 1993. Springer-Verlag. ISBN 3-540-56596-5.
	15	Peter Van Weert, Jon Sneyers, Tom Schrijvers, and Bart Demoen. Extending chr with negation as absence. In Proceedings of CHR'06, Venice, Italy, July 2006.
	16	Cristian Versari, Nadia Busi, and Roberto Gorrieri. On the expressive power of global and local priority in process calculi. In Luís Caires and Vasco Thudichum Vasconcelos, editors, CONCUR, volume 4703 of Lecture Notes in Computer Science, pages 241--255. Springer, 2007. ISBN 978-3-540-74406-1.
	17	Maria Grazia Vigliotti, Iain Phillips, and Catuscia Palamidessi. Tutorial on separation results in process calculi via leader election problems. Theor. Comput. Sci., 388 (1-3): 267--289, 2007. ISSN 0304-3975. http://dx.doi.org/10.1016/j.tcs.2007.09.001.