Istituto di Scienza e Tecnologie dell'Informazione     
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.
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

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional