Modes of convergence for term graph rewriting
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Modes of convergence for term graph rewriting. / Bahr, Patrick.
22nd International Conference on Rewriting Techniques and Applications (RTA'11). red. / Manfred Schmidt-Schauß. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011. s. 139-154 (Leibniz International Proceedings in Informatics, Bind 10).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Modes of convergence for term graph rewriting
AU - Bahr, Patrick
PY - 2011
Y1 - 2011
N2 - Term graph rewriting provides a simple mechanism to finitely represent restricted forms of infinitary term rewriting. The correspondence between infinitary term rewriting and term graph rewriting has been studied to some extent. However, this endeavour is impaired by the lack of an appropriate counterpart of infinitary rewriting on the side of term graphs. We aim to fill this gap by devising two modes of convergence based on a partial order resp. a metric on term graphs. The thus obtained structures generalise corresponding modes of convergence that are usually studied in infinitary term rewriting. We argue that this yields a common framework in which both term rewriting and term graph rewriting can be studied. In order to substantiate our claim, we compare convergence on term graphs and on terms. In particular, we show that the resulting infinitary calculi of term graph rewriting exhibit the same correspondence as we know it from term rewriting: Convergence via the partial order is a conservative extension of the metric convergence.
AB - Term graph rewriting provides a simple mechanism to finitely represent restricted forms of infinitary term rewriting. The correspondence between infinitary term rewriting and term graph rewriting has been studied to some extent. However, this endeavour is impaired by the lack of an appropriate counterpart of infinitary rewriting on the side of term graphs. We aim to fill this gap by devising two modes of convergence based on a partial order resp. a metric on term graphs. The thus obtained structures generalise corresponding modes of convergence that are usually studied in infinitary term rewriting. We argue that this yields a common framework in which both term rewriting and term graph rewriting can be studied. In order to substantiate our claim, we compare convergence on term graphs and on terms. In particular, we show that the resulting infinitary calculi of term graph rewriting exhibit the same correspondence as we know it from term rewriting: Convergence via the partial order is a conservative extension of the metric convergence.
KW - Faculty of Science
KW - term graphs
KW - partial order
KW - metric
KW - infinitary rewriting
KW - graph rewriting
U2 - 10.4230/LIPIcs.RTA.2011.139
DO - 10.4230/LIPIcs.RTA.2011.139
M3 - Article in proceedings
T3 - Leibniz International Proceedings in Informatics
SP - 139
EP - 154
BT - 22nd International Conference on Rewriting Techniques and Applications (RTA'11)
A2 - Schmidt-Schauß, Manfred
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 22nd International Conference on Rewriting Techniques and Applications
Y2 - 30 May 2011 through 1 June 2011
ER -
ID: 33638088