Confluence Modulo Equivalence in Constraint Handling Rules

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

Previous results on confluence for Constraint Handling Rules, CHR, are generalized to take into account user-defined state equivalence relations. This allows a much larger class of programs to enjoy the advantages of confluence, which include various optimization techniques and simplified correctness proofs. A new operational semantics for CHR is introduced that significantly reduces notational overhead and allows to consider confluence for programs with extra-logical and incomplete built- in predicates. Proofs of confluence are demonstrated for programs with redundant data representation, e.g., sets-as-lists, for dynamic programming algorithms with pruning as well as a Union-Find program, which are not covered by previous confluence notions for CHR.
OriginalsprogEngelsk
TitelLogic-Based Program Synthesis and Transformation : 24th International Symposium, LOPSTR 2014, Canterbury, UK, September 9-11, 2014. Revised Selected Papers
RedaktørerMaurizio Proietti, Hirohisa Seki
Publikationsdato2015
Sider41-58
ISBN (Trykt)978-3-319-17821-9
ISBN (Elektronisk) 978-3-319-17822-6
DOI
StatusUdgivet - 2015
BegivenhedLogic-Based Program Synthesis and Transformation - University of Kent, Canterbury, Canterbury, Storbritannien
Varighed: 9 sep. 201411 sep. 2014
http://www.iasi.cnr.it/events/lopstr14/

Konference

KonferenceLogic-Based Program Synthesis and Transformation
LokationUniversity of Kent, Canterbury
LandStorbritannien
ByCanterbury
Periode09/09/201411/09/2014
Internetadresse
NavnLecture Notes in Computer Science
Vol/bind8981
ISSN0302-9743

Bibliografisk note

Revised and extended version of paper first printed in preliminary proceedings 2014 (same title)

Citer dette

Christiansen, H., & Kirkeby, M. H. (2015). Confluence Modulo Equivalence in Constraint Handling Rules. I M. Proietti, & H. Seki (red.), Logic-Based Program Synthesis and Transformation: 24th International Symposium, LOPSTR 2014, Canterbury, UK, September 9-11, 2014. Revised Selected Papers (s. 41-58). Lecture Notes in Computer Science, Bind. 8981 https://doi.org/10.1007/978-3-319-17822-6_3