License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.25
URN: urn:nbn:de:0030-drops-95632
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9563/
Go to the corresponding LIPIcs Volume Portal

Brengos, Tomasz

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

pdf-format:
LIPIcs-CONCUR-2018-25.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{brengos:LIPIcs:2018:9563,
  author =	{Tomasz Brengos},
  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 =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9563},
  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}
}

Keywords: coalgebras, regular languages, omega regular languages, automata, Büchi automata, silent moves, internal moves, monads, saturation
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI