Stable Computational Semantics of Conflict-free Rewrite Systems (Partial Orders with Duplication)

Khasidashvili, Zurab and Glauert, John R. W. (2003) Stable Computational Semantics of Conflict-free Rewrite Systems (Partial Orders with Duplication). In: Rewriting Techniques and Applications. Lecture Notes in Computer Science, 2706 . Springer Berlin / Heidelberg, ESP, pp. 467-482. ISBN 978-3-540-40254-1

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

Abstract

We study orderings ?S on reductions in the style of Lévy reflecting the growth of information w.r.t. (super)stable sets S of ‘values’ (such as head-normal forms or Böhm-trees). We show that sets of co-initial reductions ordered by ?S form finitary ?-algebraic complete lattices, and hence form computation and Scott domains. As a consequence, we obtain a relativized version of the computational semantics proposed by Boudol for term rewriting systems. Furthermore, we give a pure domain-theoretic characterization of the orderings ?S in the spirit of Kahn and Plotkin’s concrete domains. These constructions are carried out in the framework of Stable Deterministic Residual Structures, which are abstract reduction systems with an axiomatized residual relations on redexes, that model all orthogonal (or conflict-free) reduction systems as well as many other interesting computation structures.

Item Type:	Book Section
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Interactive Graphics and Audio Faculty of Science > Research Groups > Computer Graphics (former - to 2018)
Depositing User:	Vishal Gautam
Date Deposited:	23 Jul 2011 15:47
Last Modified:	17 Jun 2023 00:40
URI:	https://ueaeprints.uea.ac.uk/id/eprint/22835
DOI:	10.1007/3-540-44881-0_33

Actions (login required)

View Item