Paper: Closure Properties of Coalgebra Automata (at LICS 2005)

Authors: Clemens Kupke Yde Venema

Abstract

We generalize some of the central results in automata theory to the abstraction level of coalgebras. In particular, we show that for any standard, weak pullback preserving functor F, the class of recognizable languages of F-coalgebras is closed under taking unions, intersections and projections. Our main technical result concerns a construction which transforms a given alternating F-automaton into an equivalent non-deterministic one.

BibTeX

  @InProceedings{KupkeVenema-ClosurePropertiesof,
    author = 	 {Clemens Kupke and Yde Venema},
    title = 	 {Closure Properties of Coalgebra Automata},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005)},
    year =	 {2005},
    month =	 {June}, 
    pages =      {199--208},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }