Paper Info
Title
Stable computational semantics of conflict-free rewrite systems (partial orders with duplication)
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.
Year
DOI
Venue
2003
10.1007/3-540-44881-0_33
Lecture Notes in Computer Science
Keywords
Field
DocType
algebraic complete lattice,interesting computation structure,stable deterministic residual structures,stable computational semantics,co-initial reduction,abstract reduction system,reduction system,head-normal form,form finitary,partial order,scott domain,axiomatized residual relation,lattice,complete lattice,computational semantics,semantics,normal form,reliability,ordering,head,partial ordering,stable set,deterministic approach,duplication
Discrete mathematics,Lattice (order),Computational semantics,Algorithm,Finitary,Rewriting,Complete lattice,Deterministic system (philosophy),Partially ordered set,Mathematics,Computation
Conference
Volume
ISSN
ISBN
2706
0302-9743
3-540-40254-3
Citations 
PageRank 
References 
1
0.34
22
Authors
2
Name
Order
Citations
PageRank
Zurab Khasidashvili130725.40
John R. W. Glauert2779.24