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

Bahr, P 2011, From infinitary term rewriting to cyclic term graph rewriting and back. in R Echahed (ed.), Proceedings of the 6th International Workshop on Computing with Terms and Graphs. Electronic Proceedings in Theoretical Computer Science, vol. 48, pp. 2, 6th International Workshop on Computing with Terms and Graphs, Saarbrücken, Germany, 02/04/2011. https://doi.org/10.4204/EPTCS.48

APA

Bahr, P. (2011). From infinitary term rewriting to cyclic term graph rewriting and back. In R. Echahed (Ed.), Proceedings of the 6th International Workshop on Computing with Terms and Graphs (pp. 2). Electronic Proceedings in Theoretical Computer Science Vol. 48 https://doi.org/10.4204/EPTCS.48

Vancouver

Bahr P. From infinitary term rewriting to cyclic term graph rewriting and back. In Echahed R, editor, Proceedings of the 6th International Workshop on Computing with Terms and Graphs. 2011. p. 2. (Electronic Proceedings in Theoretical Computer Science, Vol. 48). https://doi.org/10.4204/EPTCS.48

Author

Bahr, Patrick. / From infinitary term rewriting to cyclic term graph rewriting and back. Proceedings of the 6th International Workshop on Computing with Terms and Graphs. editor / Rachid Echahed. 2011. pp. 2 (Electronic Proceedings in Theoretical Computer Science, Vol. 48).

Bibtex

@inbook{dbae4dff6fd24e29bd62163a4e18dd0a,
title = "From infinitary term rewriting to cyclic term graph rewriting and back",
abstract = "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. ",
keywords = "Faculty of Science, term rewriting, term graph rewriting, infinitary rewriting",
author = "Patrick Bahr",
note = "invited talk; 6th International Workshop on Computing with Terms and Graphs ; Conference date: 02-04-2011",
year = "2011",
month = feb,
day = "11",
doi = "10.4204/EPTCS.48",
language = "English",
series = "Electronic Proceedings in Theoretical Computer Science",
publisher = "Open Publishing Association",
pages = "2",
editor = "Rachid Echahed",
booktitle = "Proceedings of the 6th International Workshop on Computing with Terms and Graphs",

}

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