Coalgebraic automata theory: basic results

Clemens Kupke, Yde Venema

Research output: Contribution to journalArticle

27 Citations (Scopus)

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 languageEnglish
Article number10
Number of pages43
JournalLogical Methods in Computer Science
Volume4
Issue number4
DOIs
Publication statusPublished - 21 Nov 2008

Keywords

  • automata
  • coalgebraic logics
  • parity games
  • fixed-point logics
  • coalgebraic semantics

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

  • Cite this