*banner
 

Modeling Timed Concurrent Systems using Generalized Ultrametrics
Xiaojun Liu, Eleftherios Matsikoudis, Edward A. Lee

Citation
Xiaojun Liu, Eleftherios Matsikoudis, Edward A. Lee. "Modeling Timed Concurrent Systems using Generalized Ultrametrics". Technical report, EECS Department, UC Berkeley, May, 2006.

Abstract
Timed concurrent systems are used in concurrent and distributed real-time software, modeling of hybrid systems, design of hardware systems (using hardware description languages), discrete-event simulation, and modeling of communication networks. They consist of concurrent components that communicate using timed signals, which are sets of (semantically) time-stamped events. The denotational semantics of such systems is traditionally formulated in a metric space. In this metric space, causal components are modeled by contracting functions. We show that this formulation excessively restricts the models of time that can be used. In particular, it cannot handle super-dense time, commonly used in hardware description languages and hybrid systems modeling, finite time lines, and time with no origin. Moreover, if we admit continuous-time and mixed signals (essential for hybrid systems modeling) or certain Zeno signals, then causality is no longer equivalent to its formalization in terms of contracting functions. In this paper, we offer an alternative semantic framework using a generalized ultrametric that overcomes these limitations.

Electronic downloads

Citation formats  
  • HTML
    Xiaojun Liu, Eleftherios Matsikoudis, Edward A. Lee. <a
    href="http://chess.eecs.berkeley.edu/pubs/120.html"
    ><i>Modeling Timed Concurrent Systems using
    Generalized Ultrametrics</i></a>, Technical
    report,  EECS Department, UC Berkeley, May, 2006.
  • Plain text
    Xiaojun Liu, Eleftherios Matsikoudis, Edward A. Lee.
    "Modeling Timed Concurrent Systems using Generalized
    Ultrametrics". Technical report,  EECS Department, UC
    Berkeley, May, 2006.
  • BibTeX
    @techreport{LiuMatsikoudisLee06_ModelingTimedConcurrentSystemsUsingGeneralizedUltrametrics,
        author = {Xiaojun Liu and Eleftherios Matsikoudis and Edward
                  A. Lee},
        title = {Modeling Timed Concurrent Systems using
                  Generalized Ultrametrics},
        institution = {EECS Department, UC Berkeley},
        month = {May},
        year = {2006},
        abstract = {Timed concurrent systems are used in concurrent
                  and distributed real-time software, modeling of
                  hybrid systems, design of hardware systems (using
                  hardware description languages), discrete-event
                  simulation, and modeling of communication
                  networks. They consist of concurrent components
                  that communicate using timed signals, which are
                  sets of (semantically) time-stamped events. The
                  denotational semantics of such systems is
                  traditionally formulated in a metric space. In
                  this metric space, causal components are modeled
                  by contracting functions. We show that this
                  formulation excessively restricts the models of
                  time that can be used. In particular, it cannot
                  handle super-dense time, commonly used in hardware
                  description languages and hybrid systems modeling,
                  finite time lines, and time with no origin.
                  Moreover, if we admit continuous-time and mixed
                  signals (essential for hybrid systems modeling) or
                  certain Zeno signals, then causality is no longer
                  equivalent to its formalization in terms of
                  contracting functions. In this paper, we offer an
                  alternative semantic framework using a generalized
                  ultrametric that overcomes these limitations.},
        URL = {http://chess.eecs.berkeley.edu/pubs/120.html}
    }
    

Posted by Mary Stewart on 15 May 2006.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess