Skip to main content

Infinitary Rewriting: Foundations Revisited

Kahrs, Stefan (2010) Infinitary Rewriting: Foundations Revisited. In: Lynch, Christopher, ed. Proceedings of the 21st International Conference on Rewriting Techniques and Applications. LIPIcs . Schloss Dagstuhl, Dagstuhl, Germany, pp. 182-196. ISBN 978-3-939897-18-7. (doi:10.4230/LIPIcs.RTA.2010.161) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:30652)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://dx.doi.org/10.4230/LIPIcs.RTA.2010.161

Abstract

Infinitary Term Rewriting allows to express infinitary terms and infinitary reductions that converge to them. As their notion of transfinite reduction in general, and as binary relations in particular two concepts have been studied in the past: strongly and weakly convergent reductions, and in the last decade research has mostly focused around the former. Finitary rewriting has a strong connection to the equational theory of its rule set: if the rewrite system is confluent this (implies consistency of the theory and) gives rise to a semi-decision procedure for the theory, and if the rewrite system is in addition terminating this becomes a decision procedure. This connection is the original reason for the study of these properties in rewriting. For infinitary rewriting there is barely an established notion of an equational theory. The reason this issue is not trivial is that such a theory would need to include some form of ``getting to limits'', and there are different options one can pursue. These options are being looked at here, as well as several alternatives for the notion of reduction relation and their relationships to these equational theories.

Item Type: Book section
DOI/Identification number: 10.4230/LIPIcs.RTA.2010.161
Uncontrolled keywords: determinacy analysis, Craig interpolants
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Stefan Kahrs
Date Deposited: 21 Sep 2012 09:49 UTC
Last Modified: 16 Nov 2021 10:08 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/30652 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.