Slim Abdennadher,
Thom Frühwirth,
and Holger Meuss.
On confluence of Constraint Handling Rules.
In CP '96: Proc. Second Intl. Conf. Principles and Practice of Constraint Programming,
volume 1118 of Lecture Notes in Computer Science,
pages 1-15,
August 1996.
Springer-Verlag.
[doi:10.1007/3-540-61551-2_62]
Keyword(s): confluence.
Abstract:
We introduce the notion of confluence for Constraint Handling Rules (CHR), a powerful language for writing constraint solvers. With CHR one simplifies and solves constraints by applying rules. Confluence guarantees that a CHR program will always compute the same result for a given set of constraints independent of which rules are applied. We give a decidable, sufficient and necessary syntactic condition for confluence. Confluence turns out to be an essential syntactical property of CHR programs for two reasons. First, confluence implies correctness (as will be shown in this paper). In a correct CHR program, application of CHR rules preserves logical equivalence of the simplified constraints. Secondly, even when the program is already correct, confluence is highly desirable. Otherwise, given some constraints, one computation may detect their inconsistency while another one may just simplify them into a still complex constraint. As a side-effect, the paper also gives soundness and completeness results for CHR programs. Due to their special nature, and in particular correctness, these theorems are stronger than what holds for the related families of (concurrent) constraint programming languages. |
@inproceedings{abd_fru_meuss_on_confluence_cp96,
author = {Slim Abdennadher and Thom Fr{\"u}hwirth and Holger Meuss},
title = { On confluence of {C}onstraint {H}andling {R}ules},
keywords = {confluence},
year = 1996,
month = aug,
booktitle = {CP '96: Proc.\ Second Intl.\ Conf.\ Principles and Practice of Constraint Programming},
location = {Cambridge, Massachusetts, USA},
city = {Cambridge, Massachusetts, USA},
series = LNCS,
volume = 1118,
publisher = SV,
pages = {1--15},
doi = {10.1007/3-540-61551-2_62},
abstract = { We introduce the notion of confluence for Constraint Handling Rules (CHR), a powerful language for writing constraint solvers. With CHR one simplifies and solves constraints by applying rules. Confluence guarantees that a CHR program will always compute the same result for a given set of constraints independent of which rules are applied. We give a decidable, sufficient and necessary syntactic condition for confluence. Confluence turns out to be an essential syntactical property of CHR programs for two reasons. First, confluence implies correctness (as will be shown in this paper). In a correct CHR program, application of CHR rules preserves logical equivalence of the simplified constraints. Secondly, even when the program is already correct, confluence is highly desirable. Otherwise, given some constraints, one computation may detect their inconsistency while another one may just simplify them into a still complex constraint. As a side-effect, the paper also gives soundness and completeness results for CHR programs. Due to their special nature, and in particular correctness, these theorems are stronger than what holds for the related families of (concurrent) constraint programming languages. },
}
Marìa Teresa Escrig Monferrer and Francisco Toledo Lobo.
Enhancing qualitative relative orientation with qualitative distance for robot path planning.
In ICTAI '96: Proc. 8th IEEE Intl. Conf. Tools with Artif. Intell.,
pages 174-182,
November 1996.
IEEE Computer Society.
[doi:10.1109/TAI.1996.560449]
@inproceedings{escrig_toledo_ictai96,
author = {Escrig Monferrer, Mar{\'i}a Teresa and Toledo Lobo, Francisco},
title = {Enhancing qualitative relative orientation with qualitative distance for robot path planning},
booktitle = {ICTAI '96: Proc.\ 8th IEEE Intl.\ Conf.\ Tools with Artif.\ Intell.},
pages = {174--182},
year = 1996,
month = nov,
doi = {10.1109/TAI.1996.560449},
publisher = {IEEE Computer Society},
}
Eric Monfroy,
Michael Rusinowitch,
and René Schott.
Implementing non-linear constraints with cooperative solvers.
In SAC '96: Proc. 1996 ACM symposium on Applied Computing,
pages 63-72,
1996.
ACM Press.
ISBN: 0-89791-820-7.
[doi:10.1145/331119.331147]
@inproceedings{monfroy_et_al_nonlinear_cooperative_sac96,
author = {Eric Monfroy and Michael Rusinowitch and Ren{\'e} Schott},
title = {Implementing non-linear constraints with cooperative solvers},
booktitle = {SAC '96: Proc. 1996 ACM symposium on Applied Computing},
year = {1996},
isbn = {0-89791-820-7},
pages = {63--72},
location = {Philadelphia, Pennsylvania, United States},
city = {Philadelphia, Pennsylvania, United States},
doi = {10.1145/331119.331147},
publisher = {ACM Press},
}