|
|
VOLUME 4, ISSUE 4, PAPER 10
|
Coalgebraic Automata Theory: Basic Results
|
©Clemens Kupke, CWI Amsterdam
©Yde Venema, University of Amsterdam, ILLC
|
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.
|
Publication date: November 21, 2008
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-4(4:10)2008
Hit Counts: 2601 |
 Creative Commons | |
