Title: The computational power and complexity of Constraint Handling Rules
Authors: Sneyers, Jon ×
Schrijvers, Tom
Demoen, Bart #
Issue Date: Feb-2009
Publisher: Association for Computing Machinery
Series Title: ACM transactions on programming languages and systems vol:31 issue:2 pages:42 p.
Article number: 8
Abstract: Constraint Handling Rules (CHR) is a high-level rule-based programming language which is increasingly used for general purposes. We introduce the CHR machine, a model of computation based on the operational semantics of CHR. Its computational power and time complexity properties are compared to those of the well-understood Turing machine and Random Access Memory machine. This allows us to prove the interesting result that every algorithm can be implemented in CHR with the best known time and space complexity. We also investigate the practical relevance of this result and the constant factors involved. Finally we expand the scope of the discussion to other (declarative) programming languages.
ISSN: 0164-0925
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
p1-sneyers.pdfMain article (draft) Published 1165KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science