A Uniform Framework for Timed Automata

Tomasz Brengos , Marco Peressotti

Abstract

Timed automata, and machines alike, currently lack a general mathematical characterisation. In this paper we provide a uniform coalgebraic understanding of these devices. This framework encompasses known behavioural equivalences for timed automata and paves the way for the extension of these notions to new timed behaviours and for the instantiation of established results from the coalgebraic theory as well. Key to this work is the use of lax functors for they allow us to model time flow as a context property and hence offer a general and expressive setting where to study timed systems: the index category encodes “how step sequences form executions” (e.g. whether steps duration get accumulated or kept distinct) whereas the base category encodes “step nature and composition” (e.g. non-determinism and labels). Finally, we develop the notion of general saturation for lax functors and show how equivalences of interest for timed behaviours are instances of this notion. This characterisation allows us to reason about the expressiveness of said notions within a uniform framework and organise them in a spectrum independent from the behavioural aspects encoded in the base category.
Author Tomasz Brengos ZAK
Tomasz Brengos,,
- Department of Algebra and Combinatorics
, Marco Peressotti
Marco Peressotti,,
-
Journal seriesLeibniz International Proceedings in Informatics, ISSN 1868-8969
Issue year2016
Vol59
Pages1-15
Publication size in sheets0.7
ConferenceThe 27th International Conference on Concurrency Theory 2016 (CONCUR 2016), 23-08-2016 - 26-08-2016, Québec City, Kanada
Keywords in Englishtimed automata, coalgebras, saturation, non-determinism
Abstract in PolishW pracy przedstawione jest kategoryjne podejście do modelowania automatów z niedyskretnym czasem jako lax funktorów.
DOIDOI:10.4230/LIPIcs.CONCUR.2016.26
URL http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16011
Languageen angielski
Score (nominal)5
ScoreMinisterial score [Punktacja MNiSW] = 0.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) [Punktacja MNiSW (2013-2016)] = 5.0, 28-11-2017, ArticleFromJournal - czasopismo zagraniczne spoza list
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


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