Abstract critical pairs and confluence of arbitrary binary relations

Rémy Haemmerlé; François Fages

doi:10.1007/978-3-540-73449-9_17

Abstract critical pairs and confluence of arbitrary binary relations

Rémy Haemmerlé, François Fages

INRIA Rocquencourt

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In a seminal paper, Huet introduced abstract properties of term rewriting systems, and the confluence analysis of terminating term rewriting systems by critical pairs computation. In this paper, we provide an abstract notion of critical pair for arbitrary binary relations and context operators. We show how this notion applies to the confluence analysis of various transition systems, ranging from classical term rewriting systems to production rules with constraints and partial control strategies, such as the Constraint Handling Rules language CHR. Interestingly, we show in all these cases that some classical critical pairs can be disregarded. The crux of these analyses is the ability to compute critical pairs between states built with general context operators, on which a bounded, not necessarily well-founded, ordering is assumed.

Original language	English
Title of host publication	Term Rewriting and Applications - 18th International Conference, RTA 2007, Proceedings
Publisher	Springer Verlag
Pages	214-228
Number of pages	15
ISBN (Print)	9783540734475
DOIs	https://doi.org/10.1007/978-3-540-73449-9_17
Publication status	Published - 1 Jan 2007
Externally published	Yes
Event	18th International Conference on Rewriting Techniques and Applications, RTA 2007 - Paris, France Duration: 26 Jun 2007 → 28 Jun 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4533 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Rewriting Techniques and Applications, RTA 2007
Country/Territory	France
City	Paris
Period	26/06/07 → 28/06/07

Access to Document

10.1007/978-3-540-73449-9_17

Cite this

Haemmerlé, R., & Fages, F. (2007). Abstract critical pairs and confluence of arbitrary binary relations. In Term Rewriting and Applications - 18th International Conference, RTA 2007, Proceedings (pp. 214-228). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4533 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73449-9_17

@inproceedings{8db97c41c6644c5299cc534af609ef79,

title = "Abstract critical pairs and confluence of arbitrary binary relations",

abstract = "In a seminal paper, Huet introduced abstract properties of term rewriting systems, and the confluence analysis of terminating term rewriting systems by critical pairs computation. In this paper, we provide an abstract notion of critical pair for arbitrary binary relations and context operators. We show how this notion applies to the confluence analysis of various transition systems, ranging from classical term rewriting systems to production rules with constraints and partial control strategies, such as the Constraint Handling Rules language CHR. Interestingly, we show in all these cases that some classical critical pairs can be disregarded. The crux of these analyses is the ability to compute critical pairs between states built with general context operators, on which a bounded, not necessarily well-founded, ordering is assumed.",

author = "R{\'e}my Haemmerl{\'e} and Fran{\c c}ois Fages",

year = "2007",

month = jan,

day = "1",

doi = "10.1007/978-3-540-73449-9\_17",

language = "English",

isbn = "9783540734475",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "214--228",

booktitle = "Term Rewriting and Applications - 18th International Conference, RTA 2007, Proceedings",

note = "18th International Conference on Rewriting Techniques and Applications, RTA 2007 ; Conference date: 26-06-2007 Through 28-06-2007",

}

Haemmerlé, R & Fages, F 2007, Abstract critical pairs and confluence of arbitrary binary relations. in Term Rewriting and Applications - 18th International Conference, RTA 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4533 LNCS, Springer Verlag, pp. 214-228, 18th International Conference on Rewriting Techniques and Applications, RTA 2007, Paris, France, 26/06/07. https://doi.org/10.1007/978-3-540-73449-9_17

Abstract critical pairs and confluence of arbitrary binary relations. / Haemmerlé, Rémy; Fages, François.
Term Rewriting and Applications - 18th International Conference, RTA 2007, Proceedings. Springer Verlag, 2007. p. 214-228 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4533 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Abstract critical pairs and confluence of arbitrary binary relations

AU - Haemmerlé, Rémy

AU - Fages, François

PY - 2007/1/1

Y1 - 2007/1/1

N2 - In a seminal paper, Huet introduced abstract properties of term rewriting systems, and the confluence analysis of terminating term rewriting systems by critical pairs computation. In this paper, we provide an abstract notion of critical pair for arbitrary binary relations and context operators. We show how this notion applies to the confluence analysis of various transition systems, ranging from classical term rewriting systems to production rules with constraints and partial control strategies, such as the Constraint Handling Rules language CHR. Interestingly, we show in all these cases that some classical critical pairs can be disregarded. The crux of these analyses is the ability to compute critical pairs between states built with general context operators, on which a bounded, not necessarily well-founded, ordering is assumed.

AB - In a seminal paper, Huet introduced abstract properties of term rewriting systems, and the confluence analysis of terminating term rewriting systems by critical pairs computation. In this paper, we provide an abstract notion of critical pair for arbitrary binary relations and context operators. We show how this notion applies to the confluence analysis of various transition systems, ranging from classical term rewriting systems to production rules with constraints and partial control strategies, such as the Constraint Handling Rules language CHR. Interestingly, we show in all these cases that some classical critical pairs can be disregarded. The crux of these analyses is the ability to compute critical pairs between states built with general context operators, on which a bounded, not necessarily well-founded, ordering is assumed.

U2 - 10.1007/978-3-540-73449-9_17

DO - 10.1007/978-3-540-73449-9_17

M3 - Conference contribution

AN - SCOPUS:38049112990

SN - 9783540734475

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 214

EP - 228

BT - Term Rewriting and Applications - 18th International Conference, RTA 2007, Proceedings

PB - Springer Verlag

T2 - 18th International Conference on Rewriting Techniques and Applications, RTA 2007

Y2 - 26 June 2007 through 28 June 2007

ER -

Haemmerlé R, Fages F. Abstract critical pairs and confluence of arbitrary binary relations. In Term Rewriting and Applications - 18th International Conference, RTA 2007, Proceedings. Springer Verlag. 2007. p. 214-228. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73449-9_17

Abstract critical pairs and confluence of arbitrary binary relations

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this