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

Tomasz Brengos

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 (ω-) 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, (0 pkt)
Issue year2018
Vol118
Pages25:1-25:18
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ę.
DOIDOI:10.4230/LIPIcs.CONCUR.2018.25
URL http://drops.dagstuhl.de/opus/volltexte/2018/9563/pdf/LIPIcs-CONCUR-2018-25.pdf
Languageen angielski
Score (nominal)0
ScoreMinisterial score = 0.0, 11-03-2019, ArticleFromJournal
Ministerial score (2013-2016) = 0.0, 11-03-2019, ArticleFromJournal - za mała objętość w arkuszach wydawniczych: 0.3
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