Abstract models of transfinite reductions
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Bahr10rta-Abstract Models of Transfinite Reductions
Final published version, 203 KB, PDF document
We investigate transfinite reductions in abstract reduction systems. To this end, we study two abstract models for transfinite reductions: a metric model generalising the usual metric approach to infinitary term rewriting and a novel partial order model. For both models we distinguish between a weak and a strong variant of convergence as known from infinitary term rewriting. Furthermore, we introduce an axiomatic model of reductions that is general enough to cover all of these models of transfinite reductions as well as the ordinary model of finite reductions. It is shown that, in this unifying axiomatic model, many basic relations between termination and confluence properties known from finite reductions still hold. The introduced models are applied to term rewriting but also to term graph rewriting. We can show that for both term rewriting as well as for term graph rewriting the partial order model forms a conservative extension to the metric model.
Original language | English |
---|---|
Title of host publication | Proceedings of the 21st International Conference on Rewriting Techniques and Applications |
Editors | Christopher Lynch |
Number of pages | 18 |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Publication date | 2010 |
Pages | 49-66 |
ISBN (Electronic) | 978-3-939897-18-7 |
DOIs | |
Publication status | Published - 2010 |
Event | 21st International Conference on Rewriting Techniques and Applications - Edinburgh, United Kingdom Duration: 11 Jul 2010 → 13 Jul 2010 |
Conference
Conference | 21st International Conference on Rewriting Techniques and Applications |
---|---|
Land | United Kingdom |
By | Edinburgh |
Periode | 11/07/2010 → 13/07/2010 |
Series | Leibniz International Proceedings in Informatics |
---|---|
Volume | 6 |
ISSN | 1868-8969 |
- Faculty of Science - infinitary rewriting, metric, partial order, abstract reduction system, axiomatic, term rewriting, graph rewriting
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 20876656