Metric semantics for true concurrent real time

Joost-Pieter KatoenJoost-Pieter Katoen, Christel BaierChristel Baier, Diego LatellaDiego Latella

DOI Link

Joost-Pieter Katoen, Christel Baier, Diego Latella
Metric semantics for true concurrent real time
Theoretical Computer Science, 254(1-2):501--542, 2001

Details
Bibtex

KurzfassungAbstract
This paper investigates the use of a complete metric space framework for providing denotational semantics to a real-time process algebra. The study is carried out in a non-interleaving setting and is based on a timed extension of Langerak's bundle event structures, a variant of Winskel's event structures. The distance function of the metric is based on the amount of time to which event structures do ‘agree’. We show that this intuitive notion of distance is a pseudo-metric (but not a metric) on the set of timed event structures. A generalisation to equivalence classes of timed event structures in which we abstract from event identities and non-executable events (events that can never occur) is shown to be a complete ultra-metric space. We present an operational semantics for the considered language and show that the metric semantics is an abstraction of it. The operational semantics is characterised by the absence of synchronisation on the advance of time as opposed to the operational semantics of most real-time calculi. The consistency between our metric and an existing cpo-based denotational semantics is briefly investigated.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@article{KBL2001,
  author  = {Joost-Pieter Katoen and Christel Baier and Diego Latella},
  title   = {Metric semantics for true concurrent real time},
  journal = {Theoretical Computer Science},
  volume  = {254},
  number  = {1-2},
  year    = {2001},
  pages   = {501--542},
  doi     = {10.1016/S0304-3975(99)00342-4}
}