A coalgebraic take on regular and $\omega$-regular behaviours

Abstract

We present a general coalgebraic setting in which we define finite and infinite behaviour with Büchi acceptance condition for systems whose type is a monad. The first part of the paper is devoted to presenting 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. The framework is instantiated on non-deterministic (Büchi) automata, tree automata and probabilistic automata.

References in corpus (4)

• Seven Sketches in Compositionality: An Invitation to Applied Category Theory
• Corecursive Algebras, Corecursive Monads and Bloom Monads
• Coalgebraic Trace Semantics for Buechi and Parity Automata
• Behavioural equivalences for timed systems