Metric semantics for true concurrent real time

Katoen J. P., Baier C., Latella D.

Consistency of semantics  Denotational semantics  (bundle) Event structure  Interleaving  Metric space  Process algebra  Real time  Semantics  True concurrency  Metrics 

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.

Source: Theoretical computer science 254 (2001): 501–542.

Publisher: Elsevier, Lausanne ;, Paesi Bassi