10.4230/LIPICS.RTA.2010.161
Kahrs, Stefan
Stefan
Kahrs
Infinitary Rewriting: Foundations Revisited
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Article
Infinitary rewriting
equivalence
Lynch, Christopher
Christopher
Lynch
2010
2010-07-06
2010-07-06
2010-07-06
en
urn:nbn:de:0030-drops-26510
10.4230/LIPIcs.RTA.2010
978-3-939897-18-7
1868-8969
10.4230/LIPIcs.RTA.2010
LIPIcs, Volume 6, RTA 2010
Proceedings of the 21st International Conference on Rewriting Techniques and Applications
2013
6
14
161
176
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Lynch, Christopher
Christopher
Lynch
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
6
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
16 pages
170403 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications, pages 161-176