{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T04:07:08Z","timestamp":1750478828459,"version":"3.41.0"},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T00:00:00Z","timestamp":1234224000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n\t  <jats:p>This paper investigates the relationship between the Logical Algorithms (LA) language of Ganzinger and McAllester and Constraint Handling Rules (CHR). We present a translation schema from LA to CHR<jats:sup>rp<\/jats:sup>: CHR with rule priorities, and show that the meta-complexity theorem for LA can be applied to a subset of CHR<jats:sup>rp<\/jats:sup> via inverse translation. Inspired by the high-level implementation proposal for Logical Algorithm by Ganzinger and McAllester and based on a new scheduling algorithm, we propose an alternative implementation for CHR<jats:sup>rp<\/jats:sup> that gives strong complexity guarantees and results in a new and accurate meta-complexity theorem for CHR<jats:sup>rp<\/jats:sup>. It is furthermore shown that the translation from Logical Algorithms to CHR<jats:sup>rp<\/jats:sup> combined with the new CHR<jats:sup>rp<\/jats:sup> implementation satisfies the required complexity for the Logical Algorithms meta-complexity result to hold.<\/jats:p>","DOI":"10.1017\/s1471068409003664","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T12:22:10Z","timestamp":1234268530000},"page":"165-212","source":"Crossref","is-referenced-by-count":1,"title":["Logical Algorithms meets CHR: A meta-complexity result for Constraint Handling Rules with rule priorities"],"prefix":"10.1017","volume":"9","author":[{"given":"LESLIE","family":"DE KONINCK","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,2,10]]},"reference":[{"key":"S1471068409003664_manual_ref-35","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/1273920.1273945","volume-title":"9th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming","author":"Tacchella","year":"2007"},{"key":"S1471068409003664_manual_ref-26","unstructured":"Proctor, M. , Neale, M. , Frandsen, M. , Griffith, S. Jr , Tirelli, E. , Meyer, F. and Verlaenen, K. 2007. Drools Documentation, Version 4.0.3. http:\/\/www.jboss.com\/products\/rules."},{"key":"S1471068409003664_manual_ref-27","doi-asserted-by":"crossref","unstructured":"Schrijvers, T. 2005. Analyses, optimizations and extensions of Constraint Handling Rules. Ph.D. thesis, K.U.Leuven, Leuven, Belgium.","DOI":"10.1007\/11562931_44"},{"key":"S1471068409003664_manual_ref-8","doi-asserted-by":"publisher","DOI":"10.1007\/11799573_11"},{"key":"S1471068409003664_manual_ref-14","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0743-1066(98)10005-5","article-title":"Theory and practice of Constraint Handling Rules","volume":"37","author":"Fr\u00fchwirth","year":"1998","journal-title":"Journal of Logic Programming"},{"key":"S1471068409003664_manual_ref-30","doi-asserted-by":"crossref","unstructured":"Sneyers, J. 2008. Optimizing compilation and computational complexity of Constraint Handling Rules. Ph.D. thesis, K.U.Leuven, Leuven, Belgium.","DOI":"10.1007\/978-3-642-02846-5_41"},{"key":"S1471068409003664_manual_ref-32","first-page":"182","volume-title":"20th Workshop on Logic Programming","author":"Sneyers","year":"2006"},{"key":"S1471068409003664_manual_ref-24","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/978-3-540-89982-2_43","volume-title":"24th International Conference on Logic Programming","author":"Pilozzi","year":"2008"},{"key":"S1471068409003664_manual_ref-17","first-page":"547","volume-title":"8th International Conference on Principles of Knowledge Representation and Reasoning","author":"Fr\u00fchwirth","year":"2002"},{"key":"S1471068409003664_manual_ref-20","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/3-540-45619-8_15","volume-title":"18th International Conference on Logic Programming","author":"Ganzinger","year":"2002"},{"key":"S1471068409003664_manual_ref-25","first-page":"30","volume-title":"9th International Workshop on Termination","author":"Pilozzi","year":"2007"},{"key":"S1471068409003664_manual_ref-5","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-540-74610-2_15","volume-title":"23rd International Conference on Logic Programming","author":"De Koninck","year":"2007"},{"key":"S1471068409003664_manual_ref-9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27775-0_7"},{"key":"S1471068409003664_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48685-2_18"},{"key":"S1471068409003664_manual_ref-6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1273920.1273924","volume-title":"9th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming","author":"De Koninck","year":"2007"},{"key":"S1471068409003664_manual_ref-23","first-page":"685","volume-title":"8th National Conference on Artificial Intelligence","author":"Miranker","year":"1990"},{"key":"S1471068409003664_manual_ref-16","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/3-540-44654-0_15","volume-title":"Joint ERCIM\/Compulog Net Workshop on New Trends in Contraints","author":"Fr\u00fchwirth","year":"2000"},{"key":"S1471068409003664_manual_ref-7","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/978-3-540-78969-7_5","volume-title":"9th International Symposium on Functional and Logic Programming","author":"De Koninck","year":"2008"},{"key":"S1471068409003664_manual_ref-13","unstructured":"Friedman-Hill, E. 2007. JESS 7.0p2: The rule engine for the Java platform. http:\/\/herzberg.ca.sandia.gov\/jess."},{"key":"S1471068409003664_manual_ref-11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(82)90020-0","article-title":"Rete: A fast algorithm for the many pattern\/many object pattern match problem","volume":"19","author":"Forgy","year":"1982","journal-title":"Artificial Intelligence"},{"key":"S1471068409003664_manual_ref-15","first-page":"298","volume-title":"New Trends in Constraints, Joint ERCIM\/Compulog Net Workshop, Paphos, Cyprus, October 1999, Selected papers","author":"Fr\u00fchwirth","year":"2000"},{"key":"S1471068409003664_manual_ref-37","first-page":"77","volume-title":"4th Workshop on Constraint Handling Rules","author":"Voets","year":"2007"},{"key":"S1471068409003664_manual_ref-12","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"Journal of the ACM"},{"key":"S1471068409003664_manual_ref-1","first-page":"33","volume-title":"4th Workshop on Constraint Handling Rules","author":"Betz","year":"2007"},{"key":"S1471068409003664_manual_ref-10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74610-2_16"},{"key":"S1471068409003664_manual_ref-19","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/3-540-45744-5_44","volume-title":"1st International Joint Conference on Automated Reasoning","author":"Ganzinger","year":"2001"},{"key":"S1471068409003664_manual_ref-28","first-page":"1","volume-title":"First Workshop on Constraint Handling Rules: Selected Contributions","author":"Schrijvers","year":"2004"},{"key":"S1471068409003664_manual_ref-29","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068405002541"},{"key":"S1471068409003664_manual_ref-31","first-page":"3","volume-title":"2nd Workshop on Constraint Handling Rules","author":"Sneyers","year":"2005"},{"key":"S1471068409003664_manual_ref-2","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1017\/S1471068405002395","article-title":"CHR grammars","volume":"5","author":"Christiansen","year":"2005","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068409003664_manual_ref-33","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/11799573_8","volume-title":"22nd International Conference on Logic Programming","author":"Sneyers","year":"2006"},{"key":"S1471068409003664_manual_ref-34","doi-asserted-by":"crossref","unstructured":"Sneyers, J. , Schrijvers, T. and Demoen, B. 2008. The computational power and complexity of Constraint Handling Rules. http:\/\/www.cs.kuleuven.be\/~jon\/ \u2013 Submitted to ACM TOPLAS.","DOI":"10.1145\/1462166.1462169"},{"key":"S1471068409003664_manual_ref-21","unstructured":"Holzbaur, C. and Fr\u00fchwirth, T. 1998. Constraint Handling Rules reference manual, release 2.2. In Technical Report TR-98-01, \u00d6sterreichisches Forschungsinstitut f\u00fcr Artificial Intelligence, Wien."},{"key":"S1471068409003664_manual_ref-22","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/3-540-48294-6_21","volume-title":"6th International Symposium on Static Analysis","author":"McAllester","year":"1999"},{"key":"S1471068409003664_manual_ref-4","unstructured":"De Koninck, L. 2007. Mergeable schedules for lazy matching. In Technical Report CW 505, Department of Computer Science, K.U.Leuven."},{"volume-title":"Quantitative Aspects of Programming Languages, Selected Papers","year":"2002","author":"Fr\u00fchwirth","key":"S1471068409003664_manual_ref-18"},{"key":"S1471068409003664_manual_ref-36","first-page":"125","volume-title":"3rd Workshop on Constraint Handling Rules","author":"Van Weert","year":"2006"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068409003664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T21:54:02Z","timestamp":1750456442000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068409003664\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,10]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["S1471068409003664"],"URL":"https:\/\/doi.org\/10.1017\/s1471068409003664","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2009,2,10]]}}}