Inverardi P., Venturini Z. Rational rewriting. In: MFCS '94 - 19th International Symposium MFCS'94 (Kosice, Slovakia, August 1994). Proceedings, pp. 433 - 452. I. Privara, B. Rovan, P. Ruzicka (eds.). (Lecture notes in computer science, vol. 841). Springer, 1994. |

Abstract (English) |
So far, the works in this area have tried to define suitable properties of non-terminating relations in order to guarantee that the intended infinite term can be reached as the limit of w-converging derivations. The main advantage of these approaches is the generality of the framework with respect to the set of infinite definable terms: no a priori assumption is made on the set of definable infinite data structure. Restrictions instead apply on the kind of infinite derivations they can deal with (top erminating/strongly convergent) and on the term rewriting system, in order to guarantee the reachability of the infinite terms within w-steps. To this respect the restrictions are quite heavy since only left-linear (orthogonal) term rewriting systems can be managed. In this paper we propose a different approach based on the following consideration: in the above mentioned papers the need for considering non-terminating relations is a side effect of the definitional mechanism for infinite terms. That is the only way to deal with infinite terms is by giving the rules for constructing them. | |

Subject | Software F.3.1 Specifying and Verifying and Reasoning about Programs |

1) Download Document PDF |

Open access Restricted Private