Finitary Logics for Coalgebras with Branching

The purpose of this dissertation is to further previous work on coalgebras as infinite statebased transition systems and their logical characterisation with particular focus on infinite regular behaviour and branching. Finite trace semantics is well understood [DR95] for nondeterministic labelled transition systems, and has recently [Jac04, HJS06] been generalised to a coalgebraic level where monads act as branching types for instance, of nondeterministic choice. Finite trace semantics then arises through an inductive construction in the Kleisli-category of the monad. We provide a more comprehensive definition of finite trace semantics, allowing for finitary branching types in Chapter 5. In Chapter 6 we carry over the ideas behind our definition of finite trace semantics to define infinite trace semantics. Coalgebraic logics [Mos99] provide one approach to characterising states in coalgebras up to bisimilarity. Coalgebraic logics are Boolean logics with the modality r. We define the Boolean dual of r in the negation-free fragment of finitary coalgebraic logics in Chapter 7, showing that finitary coalgebraic logics are essentially negation free. Our proof is largely based on the previously established completeness of finitary coalgebraic logics [KKV08]. Finite trace semantics induces the notion of finite trace equivalence. In Chapter 8 we define coalgebraic logics for many relevant branching and transition types characterising states of coalgebras with branching up to finite trace equivalence. Under further assumptions we show that these logics are expressive. Coalgebra automata allow us to state finitary properties over infinite structures essentially by a fix-point style construction. We use the dualisation of r from Chapter 7 to prove that coalgebra automata are closed under complementation in Chapter 10. This result completes a Rabin style [Rab69] correspondence between finitary coalgebraic logics and coalgebra automata for finitary transition types, begun in [Ven04, KV05]. The semantics of coalgebra automata is given in terms of parity graph games [GTW02]. In Chapter 9 we show how to structure parity graph games into rounds using the notion of players power [vB02] and how to normalise the interaction pattern between the players per round. From the latter we obtain the coinductive principle of game bisimulation. Languages accepted by coalgebra automata are called regular. Regularity is commonly [Sip96, HMU03] disproved using the pumping lemma for regular languages. We define regular languages of coalgebras and prove a pumping lemma for these languages in Chapter 11.