Metric Semantics from Partial Order Semantics

Christel BaierChristel Baier, Mila E. Majster-CederbaumMila E. Majster-Cederbaum

DOI Link

Christel Baier, Mila E. Majster-Cederbaum
Metric Semantics from Partial Order Semantics
Acta Informatica, 34(9):701--735, 1997

Details
Bibtex

KurzfassungAbstract
In dealing with denotational semantics of programming languages partial orders resp. metric spaces have been used with great benefit in order to provide a meaning to recursive and repetitive constructs. This paper presents two methods to define a metric on a subset M of a complete partial order D such that M is a complete metric spaces and the metric semantics on M coincides with the partial order semantics on D when the same semantic operators are used. The first method is to add a ‘length’ on a complete partial order which means a function ρ: D → N_0 ∪{∞} of increasing power. The second is based on the ideas of [11] and uses pseudo rank orderings, i.e. monotone sequences of monotone functions π_n: D → D. We show that SFP domains can be characterized as special kinds of rank orderded cpo’s. We also discuss the connection between the Lawson topology and the topology induced by the metric.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@article{BM1997,
  author  = {Christel Baier and Mila E. Majster-Cederbaum},
  title   = {Metric Semantics from Partial Order Semantics},
  journal = {Acta Informatica},
  volume  = {34},
  number  = {9},
  year    = {1997},
  pages   = {701--735},
  doi     = {10.1007/s002360050104}
}