Coalgebraic automata theory: basic results
We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of the theory of coalgebra automata. In particular, we prove the following results for any functor F 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 an F-automaton accepts some coalgebra it accepts a finite one of bounded size. Our main technical result concerns an explicit construction which transforms a given alternating F-automaton into an equivalent nondeterministic one, of bounded size.
|Coalgebra, Automata and Logic, Parity Games|
|Models of Computation (acm F.1.1), Formal Languages (acm F.4.3), Semantics of Programming Languages (acm F.3.2)|
|Logic in computer science (msc 03B70), Algebraic theory of languages and automata (msc 68Q70), Formal languages and automata (msc 68Q45)|
|Software (theme 1)|
|Software Engineering [SEN]|
Kupke, C.A, & Venema, Y. (2007). Coalgebraic automata theory: basic results. Software Engineering [SEN]. CWI.