Kupke, C. and Venema, Y. - Coalgebraic Automata Theory: Basic Results

lmcs:1203 - Logical Methods in Computer Science, November 21, 2008, Volume 4, Issue 4
Coalgebraic Automata Theory: Basic Results

Authors: Kupke, C. and Venema, Y.

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.

Source : oai:arXiv.org:0811.1976
DOI : 10.2168/LMCS-4(4:10)2008
Volume: Volume 4, Issue 4
Published on: November 21, 2008
Submitted on: January 17, 2007
Keywords: Computer Science - Logic in Computer Science,F.1.1,F.4.3,F.3.2


Consultation statistics

This page has been seen 98 times.
This article's PDF has been downloaded 40 times.