### Abstract

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 |

### Fingerprint

### Keywords

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

### Cite this

*Logical Methods in Computer Science*,

*4*(4), [10]. https://doi.org/10.2168/LMCS-4(4:10)2008

}

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

**Coalgebraic automata theory : basic results.** / Kupke, Clemens; Venema, Yde .

Research output: Contribution to journal › Article

TY - JOUR

T1 - Coalgebraic automata theory

T2 - Logical Methods in Computer Science

AU - Kupke, Clemens

AU - Venema, Yde

PY - 2008/11/21

Y1 - 2008/11/21

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

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

KW - automata

KW - coalgebraic logics

KW - parity games

KW - ﬁxed-point logics

KW - coalgebraic semantics

U2 - 10.2168/LMCS-4(4:10)2008

DO - 10.2168/LMCS-4(4:10)2008

M3 - Article

VL - 4

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

SN - 1860-5974

IS - 4

M1 - 10

ER -