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

Z. Khasidashvili, J. R. W. Glauert

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Citation (Scopus)

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.
Original languageEnglish
Title of host publicationRewriting Techniques and Applications
EditorsRobert Nieuwenhuis
PublisherSpringer Berlin / Heidelberg
Pages467-482
Number of pages16
Volume2706
ISBN (Print)978-3-540-40254-1
DOIs
Publication statusPublished - 2003
Event14th International Conference, RTA 2003 - Valencia, Spain
Duration: 9 Jun 200311 Jun 2003

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg

Conference

Conference14th International Conference, RTA 2003
CountrySpain
CityValencia
Period9/06/0311/06/03

Cite this