An abstract concept of optimal implementation

Khasidashvili, Zurab and Glauert, John R. W. (2003) An abstract concept of optimal implementation. Electronic Notes in Theoretical Computer Science, 86 (4). pp. 689-713. ISSN 1571-0661

Full text not available from this repository. (Request a copy)

Abstract

In previous works, we introduced Stable Deterministic Residual Structures (SDRSs), Abstract Reduction Systems with an axiomatized residual relation which model orthogonal term and graph rewriting systems, and Deterministic Family Structures (DFSs), which add an axiomatized notion of redex-family to capture known sharing concepts in the ?-calculus and other orthogonal rewrite systems. In this paper, we introduce and study a concept of implementation of DFSs. We show that for any DFS F, its implementation FI is a non-duplicating DFSs with zig-zag as the family relation, where zig-zag is simply the symmetric and transitive closure of the residual relation on redexes with histories. Further, we show that sharing is compositional: the sharing in a DFS F can be decomposed into a weaker sharing F' (such as zig-zag) and a sharing in the implementation F'I of F' stronger than zig-zag. These results require study of the family relation in non-duplicating SDRSs. We show that zig-zag forms a family-relation in every non-duplicating SDRS, and that it is the only separable family relation in such SDRSs.

Item Type:	Article
Additional Information:	WRS 2003, 3rd International Workshop on Reduction Strategies in Rewriting and Programming - Final Proceedings
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computer Graphics (former - to 2018) Faculty of Science > Research Groups > Interactive Graphics and Audio
Depositing User:	Vishal Gautam
Date Deposited:	03 Mar 2011 12:42
Last Modified:	16 Jun 2023 23:42
URI:	https://ueaeprints.uea.ac.uk/id/eprint/22840
DOI:	10.1016/S1571-0661(05)82618-0

Actions (login required)

View Item