From infinitary term rewriting to cyclic term graph rewriting and back
Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research
Standard
From infinitary term rewriting to cyclic term graph rewriting and back. / Bahr, Patrick.
Proceedings of the 6th International Workshop on Computing with Terms and Graphs. ed. / Rachid Echahed. 2011. p. 2 (Electronic Proceedings in Theoretical Computer Science, Vol. 48).Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - ABST
T1 - From infinitary term rewriting to cyclic term graph rewriting and back
AU - Bahr, Patrick
N1 - invited talk
PY - 2011/2/11
Y1 - 2011/2/11
N2 - Cyclic term graph rewriting has been shown to be adequate forsimulating certain forms of infinitary term rewriting. These formsare, however, quite restrictive and it would be beneficial to liftthese restriction at least for a limited class of rewritingsystems. In order to better understand the correspondences betweeninfinite reduction sequences over terms and finite reductions overcyclic term graphs, we explore different variants of infinitary termgraph rewriting calculi.To this end, we study different modes of convergence for term graphrewriting that generalise the modes of convergence usually consideredin infinitary term rewriting. After discussing several differentalternatives, we identify a complete semilattice on term graphs andderive from it a complete metric space on term graphs. Equipped withthese structures, we can -- analogously to the term rewriting case --define both a metric and a partial order model of infinitary termgraph rewriting. The resulting calculi of infinitary term graphrewriting reveal properties similar to the corresponding infinitaryterm rewriting calculi.
AB - Cyclic term graph rewriting has been shown to be adequate forsimulating certain forms of infinitary term rewriting. These formsare, however, quite restrictive and it would be beneficial to liftthese restriction at least for a limited class of rewritingsystems. In order to better understand the correspondences betweeninfinite reduction sequences over terms and finite reductions overcyclic term graphs, we explore different variants of infinitary termgraph rewriting calculi.To this end, we study different modes of convergence for term graphrewriting that generalise the modes of convergence usually consideredin infinitary term rewriting. After discussing several differentalternatives, we identify a complete semilattice on term graphs andderive from it a complete metric space on term graphs. Equipped withthese structures, we can -- analogously to the term rewriting case --define both a metric and a partial order model of infinitary termgraph rewriting. The resulting calculi of infinitary term graphrewriting reveal properties similar to the corresponding infinitaryterm rewriting calculi.
KW - Faculty of Science
KW - term rewriting
KW - term graph rewriting
KW - infinitary rewriting
U2 - 10.4204/EPTCS.48
DO - 10.4204/EPTCS.48
M3 - Conference abstract in proceedings
T3 - Electronic Proceedings in Theoretical Computer Science
SP - 2
BT - Proceedings of the 6th International Workshop on Computing with Terms and Graphs
A2 - Echahed, Rachid
T2 - 6th International Workshop on Computing with Terms and Graphs
Y2 - 2 April 2011
ER -
ID: 34445060