Relative Normalization in Deterministic Residual Structures

John R. W. Glauert, Zurab Khasidashvili

Research output: Chapter in Book/Report/Conference proceedingChapter

19 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationTrees in Algebra and Programming — CAAP '96
EditorsHélène Kirchner
Place of PublicationBerlin / Heidelberg
Number of pages16
Publication statusPublished - 1996
Event19th International Colloquium on Trees in Algebra and Programming (CAAP'96) -
Duration: 1 Jan 1996 → …

Publication series

NameLecture Notes in Computer Science


Conference19th International Colloquium on Trees in Algebra and Programming (CAAP'96)
Period1/01/96 → …

Cite this