From infinitary term rewriting to cyclic term graph rewriting and back

Patrick Bahr

doi:10.4204/EPTCS.48

From infinitary term rewriting to cyclic term graph rewriting and back

Patrick Bahr

Datalogisk Institut

1278 Downloads (Pure)

Abstract

Cyclic term graph rewriting has been shown to be adequate for
simulating certain forms of infinitary term rewriting. These forms
are, however, quite restrictive and it would be beneficial to lift
these restriction at least for a limited class of rewriting
systems. In order to better understand the correspondences between
infinite reduction sequences over terms and finite reductions over
cyclic term graphs, we explore different variants of infinitary term
graph rewriting calculi.

To this end, we study different modes of convergence for term graph
rewriting that generalise the modes of convergence usually considered
in infinitary term rewriting. After discussing several different
alternatives, we identify a complete semilattice on term graphs and
derive from it a complete metric space on term graphs. Equipped with
these structures, we can -- analogously to the term rewriting case --
define both a metric and a partial order model of infinitary term
graph rewriting. The resulting calculi of infinitary term graph
rewriting reveal properties similar to the corresponding infinitary
term rewriting calculi.

Originalsprog	Engelsk
Titel	Proceedings of the 6th International Workshop on Computing with Terms and Graphs
Redaktører	Rachid Echahed
Antal sider	1
Publikationsdato	11 feb. 2011
Sider	2
DOI	https://doi.org/10.4204/EPTCS.48
Status	Udgivet - 11 feb. 2011
Begivenhed	6th International Workshop on Computing with Terms and Graphs - Saarbrücken, Tyskland Varighed: 2 apr. 2011 → …

Workshop

Workshop	6th International Workshop on Computing with Terms and Graphs
Land/Område	Tyskland
By	Saarbrücken
Periode	02/04/2011 → …

Navn	Electronic Proceedings in Theoretical Computer Science
Vol/bind	48
ISSN	2075-2180

Emneord

Det Natur- og Biovidenskabelige Fakultet

Adgang til dokumentet

10.4204/EPTCS.48Licens: CC BY

Bahr_2011_ABSTRACT_From_infinitaryForlagets udgivne version, 17,3 KBLicens: CC BY

Citationsformater

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

@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",

}

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 -