From infinitary term rewriting to cyclic term graph rewriting and back
Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research
Documents
- Bahr_2011_ABSTRACT_From_infinitary
Final published version, 17.3 KB, PDF document
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.
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 6th International Workshop on Computing with Terms and Graphs |
Editors | Rachid Echahed |
Number of pages | 1 |
Publication date | 11 Feb 2011 |
Pages | 2 |
DOIs | |
Publication status | Published - 11 Feb 2011 |
Event | 6th International Workshop on Computing with Terms and Graphs - Saarbrücken, Germany Duration: 2 Apr 2011 → … |
Workshop
Workshop | 6th International Workshop on Computing with Terms and Graphs |
---|---|
Land | Germany |
By | Saarbrücken |
Periode | 02/04/2011 → … |
Series | Electronic Proceedings in Theoretical Computer Science |
---|---|
Volume | 48 |
ISSN | 2075-2180 |
Bibliographical note
invited talk
- Faculty of Science - term rewriting, term graph rewriting, infinitary rewriting
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 34445060