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

Tomasz Brengos


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 (ω-) behaviour. We end the paper with coalgebraic Kleene-type theorems for (ω-) regular input. We discuss the setting in the context of non-deterministic (tree) automata and Segala automata.
Author Tomasz Brengos (FMIS / DAC)
Tomasz Brengos,,
- Department of Algebra and Combinatorics
Journal seriesLeibniz International Proceedings in Informatics, ISSN 1868-8969
Issue year2018
Publication size in sheets0.3
ConferenceThe 29th International Conference on Concurrency Theory (CONCUR 2018), 04-09-2018 - 07-09-2018, Beijing, Chiny
Keywords in Polishkoalgebry, języki regularne, języki omega regularne, automaty, automaty Buchiego, nieme kroki, monady, nasycenie
Keywords in Englishcoalgebras, regular languages, omega regular languages, automata, Büchi automata, silent moves, internal moves, monads, saturation
Abstract in PolishPrzedstawiono kategoryjny opis języków regularnych i omega regularnych oraz ich charakteryzację.
URL http://drops.dagstuhl.de/opus/volltexte/2018/9563/pdf/LIPIcs-CONCUR-2018-25.pdf
Languageen angielski
Score (nominal)15
Score sourcejournalIndex
ScoreMinisterial score = 15.0, 15-04-2020, ArticleFromJournal
Citation count*
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.
Are you sure?