Behavioural equivalences for timed systems

Tomasz Brengos , Marco Peressotti

Abstract

Timed transition systems are behavioural models that include an explicit treatment of time flow and are used to formalise the semantics of several foundational process calculi and automata. Despite their relevance, a general mathematical characterisation of timed transition systems and their behavioural theory is still missing. We introduce the first uniform framework for timed behavioural models that encompasses known behavioural equivalences such as timed bisimulations, timed language equivalences as well as their weak and time-abstract counterparts. All these notions of equivalences are naturally organised by their discriminating power in a spectrum. We prove that this result does not depend on the type of the systems under scrutiny: it holds for any generalisation of timed transition system. We instantiate our framework to timed transition systems and their quantitative extensions such as timed probabilistic systems.
Author Tomasz Brengos (FMIS / DAC)
Tomasz Brengos,,
- Department of Algebra and Combinatorics
, Marco Peressotti
Marco Peressotti,,
-
Journal seriesLogical Methods in Computer Science, ISSN 1860-5974, (A 25 pkt)
Issue year2019
Vol15
No1
Pages1-41
Publication size in sheets2
Keywords in PolishKoalgebry, laks funktory, uogólniona saturacja, czasowe równoważności, czasowa równoważność języków, czasowe automaty probabilistyczne
Keywords in EnglishCoalgebras, lax functors, general saturation, timed behavioural equivalence, timed language equivalence, timed probabilistic automata
ASJC Classification1700 General Computer Science; 2614 Theoretical Computer Science
Abstract in PolishWprowadzamy ogólny język opisu równoważności czasowych systemów z dyskretnym i niedyskretnym czasem. Głównym filarem teorii jest rozwinięte w pracy uogólnienie saturacji systemu.
DOIDOI:10.23638/LMCS-15(1:17)2019
URL https://www.researchgate.net/publication/321347617_Behavioural_equivalences_for_timed_systems
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 08-07-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2017 = 1.223; WoS Impact Factor: 2017 = 0.508 (2) - 2017=0.685 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back