License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.49
URN: urn:nbn:de:0030-drops-26445
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2644/
Go to the corresponding LIPIcs Volume Portal

Bahr, Patrick

Abstract Models of Transfinite Reductions

pdf-format:
10002.BahrPatrick.2644.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bahr:LIPIcs:2010:2644,
  author =	{Patrick Bahr},
  title =	{{Abstract Models of Transfinite Reductions}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{49--66},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2644},
  URN =		{urn:nbn:de:0030-drops-26445},
  doi =		{10.4230/LIPIcs.RTA.2010.49},
  annote =	{Keywords: Infinitary rewriting, metric, partial order, abstract   reduction system, axiomatic, term rewriting, graph rewriting}
}

Keywords: Infinitary rewriting, metric, partial order, abstract reduction system, axiomatic, term rewriting, graph rewriting
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI