Abstract models of transfinite reductions

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Patrick Bahr
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.
OriginalsprogEngelsk
TitelProceedings of the 21st International Conference on Rewriting Techniques and Applications
RedaktørerChristopher Lynch
Antal sider18
ForlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato2010
Sider49-66
ISBN (Elektronisk)978-3-939897-18-7
DOI
StatusUdgivet - 2010
Begivenhed21st International Conference on Rewriting Techniques and Applications - Edinburgh, Storbritannien
Varighed: 11 jul. 201013 jul. 2010

Konference

Konference21st International Conference on Rewriting Techniques and Applications
LandStorbritannien
ByEdinburgh
Periode11/07/201013/07/2010
NavnLeibniz International Proceedings in Informatics
Vol/bind6
ISSN1868-8969

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 20876656