### 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.

Original language | English |
---|---|

Article number | 10 |

Number of pages | 43 |

Journal | Logical Methods in Computer Science |

Volume | 4 |

Issue number | 4 |

DOIs | |

Publication status | Published - 21 Nov 2008 |

### Keywords

- automata
- coalgebraic logics
- parity games
- ﬁxed-point logics
- coalgebraic semantics

## Fingerprint Dive into the research topics of 'Coalgebraic automata theory: basic results'. Together they form a unique fingerprint.

## Cite this

Kupke, C., & Venema, Y. (2008). Coalgebraic automata theory: basic results.

*Logical Methods in Computer Science*,*4*(4), [10]. https://doi.org/10.2168/LMCS-4(4:10)2008