Coalgebraic Automata Theory: Basic Results

Abstract

We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks. We show that the class of recognizable languages of F-coalgebras is closed under taking unions, intersections, and projections. We also prove that if a nondeterministic F-automaton accepts some coalgebra it accepts a finite one of the size of the automaton. Our main technical result concerns an explicit construction which transforms a given alternating F-automaton into an equivalent nondeterministic one, whose size is exponentially bound by the size of the original automaton.

43 pages

Cited by in corpus (6)

• Completeness for the coalgebraic cover modality
• Non-Deterministic Kleene Coalgebras
• Disjunctive bases: normal forms and model theory for modal logics
• Some model theory for the modal $\mu$-calculus: syntactic characterisations of semantic properties
• On the size of disjunctive formulas in the $\mu$-calculus
• Moss' logic for ordered coalgebras