Metric semantics for true concurrent real time

Joost-Pieter Katoen, Christel Baier, Diego Latella

    Research output: Contribution to journalArticleAcademicpeer-review

    18 Citations (Scopus)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)501-542
    Number of pages42
    JournalTheoretical computer science
    Volume254
    Issue number1-2
    DOIs
    Publication statusPublished - 2001

    Keywords

    • FMT-NIM: NON-INTERLEAVING MODELS
    • FMT-SEMANTICS
    • Consistency of semantics
    • Denotational semantics
    • (bundle) Event structure
    • Interleaving
    • Metric space
    • Process algebra
    • Real time
    • Semantics
    • True concurrency

    Fingerprint Dive into the research topics of 'Metric semantics for true concurrent real time'. Together they form a unique fingerprint.

    Cite this