Metric Semantics from Partial Order Semantics

From International Center for Computational Logic

Toggle side column

Metric Semantics from Partial Order Semantics

Christel BaierChristel Baier,  Mila E. Majster-CederbaumMila E. Majster-Cederbaum
Christel Baier, Mila E. Majster-Cederbaum
Metric Semantics from Partial Order Semantics
Acta Informatica, 34(9):701--735, 1997
  • 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}
}