DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2018.25

A Coalgebraic Take on Regular and omega-Regular Behaviour for Systems with Internal Moves

Authors: Tomasz Brengos

Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)

Abstract

We present a general coalgebraic setting in which we define finite and infinite behaviour with Büchi acceptance condition for systems with internal moves. Since systems with internal moves are defined here as coalgebras for a monad, in the first part of the paper we present a construction of a monad suitable for modelling (in)finite behaviour. The second part of the paper focuses on presenting the concepts of a (coalgebraic) automaton and its (omega-) behaviour. We end the paper with coalgebraic Kleene-type theorems for (omega-) regular input. We discuss the setting in the context of non-deterministic (tree) automata and Segala automata.

Cite as

Tomasz Brengos. A Coalgebraic Take on Regular and omega-Regular Behaviour for Systems with Internal Moves. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brengos:LIPIcs.CONCUR.2018.25,
  author =	{Brengos, Tomasz},
  title =	{{A Coalgebraic Take on Regular and omega-Regular Behaviour for Systems with Internal Moves}},
  booktitle =	{29th International Conference on Concurrency Theory (CONCUR 2018)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Schewe, Sven and Zhang, Lijun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.25},
  URN =		{urn:nbn:de:0030-drops-95632},
  doi =		{10.4230/LIPIcs.CONCUR.2018.25},
  annote =	{Keywords: coalgebras, regular languages, omega regular languages, automata, B\"{u}chi automata, silent moves, internal moves, monads, saturation}
}

Document

DOI: 10.4230/LIPIcs.CONCUR.2016.26

A Uniform Framework for Timed Automata

Authors: Tomasz Brengos and Marco Peressotti

Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)

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.

Cite as

Tomasz Brengos and Marco Peressotti. A Uniform Framework for Timed Automata. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{brengos_et_al:LIPIcs.CONCUR.2016.26,
  author =	{Brengos, Tomasz and Peressotti, Marco},
  title =	{{A Uniform Framework for Timed Automata}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Desharnais, Jos\'{e}e and Jagadeesan, Radha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.26},
  URN =		{urn:nbn:de:0030-drops-61690},
  doi =		{10.4230/LIPIcs.CONCUR.2016.26},
  annote =	{Keywords: coalgebras, lax functors, general saturation, timed behavioural equivalence, timed language equivalence}
}

Search Results

Documents authored by Brengos, Tomasz

A Coalgebraic Take on Regular and omega-Regular Behaviour for Systems with Internal Moves

Abstract

Cite as

A Uniform Framework for Timed Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message