PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Kaoten J., Baier C., Latella D. Metric semantics for true concurrent real time. In: Theoretical Computer Science, vol. 254 pp. 501 - 542. Elsevier Science Inc, 2001.
 
 
Abstract
(English)
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.
Subject Consistency of semantics
Denotational semantics
(bundle) Event structure
Interleaving
Metric space
Process algebra
Real time
Semantics
True concurrency
D.2.8 Metrics


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional