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

Zurab Khasidashvili, John R. W. Glauert

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Citation (Scopus)


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
Number of pages16
ISBN (Print)978-3-540-40254-1
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


Conference14th International Conference, RTA 2003

Cite this