Relative Normalization in Deterministic Residual Structures

Glauert, John R. W. and Khasidashvili, Zurab (1996) Relative Normalization in Deterministic Residual Structures. In: Trees in Algebra and Programming — CAAP '96. Lecture Notes in Computer Science, 1059 . Springer, Berlin / Heidelberg, pp. 180-195.

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

Abstract

This paper generalizes the Huet and Lévy theory of normalization by neededness to an abstract setting. We define Stable Deterministic Residual Structures (SDRS) and Deterministic Family Structures (DFS) by axiomatizing some properties of the residual relation and the family relation on redexes in an Abstract Rewriting System. We present two proofs of the Relative Normalization Theorem, one for SDRSs for regular stable sets, and another for DFSs for all stable sets of desirable ‘normal forms’. We further prove the Relative Optimality Theorem for DFSs. We extend this result to deterministic Computation Structures which are deterministic Event Structures with an extra relation expressing self-essentiality.

Item Type:	Book Section
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:	EPrints Services
Date Deposited:	01 Oct 2010 13:41
Last Modified:	10 Jan 2024 01:17
URI:	https://ueaeprints.uea.ac.uk/id/eprint/3192
DOI:	10.1007/3-540-61064-2_37

Actions (login required)

View Item