Kupke, Clemens and Venema, Yde (2008) Coalgebraic automata theory : basic results. Logical Methods in Computer Science, 4 (4). ISSN 1860-5974Full text not available in this repository. (Request a copy from the Strathclyde author)
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.
|Keywords:||automata, coalgebraic logics , parity games, ﬁxed-point logics, coalgebraic semantics , Electronic computers. Computer science, Computer Science(all), Theoretical Computer Science|
|Subjects:||Science > Mathematics > Electronic computers. Computer science|
|Department:||Faculty of Science > Computer and Information Sciences|
|Depositing user:||Pure Administrator|
|Date Deposited:||20 Feb 2013 10:53|
|Last modified:||22 Mar 2017 12:35|