µ-Bicomplete Categories and Parity Games
Santocanale, Luigi
HAL, Report N°: RR-1281-02 / Harvested from HAL
For an arbitrary category, we consider the least class of functors con- taining the projections and closed under finite products, finite coproducts, parameterized initial algebras and parameterized final coalgebras, i.e. the class of functors that are definable by μ-terms. We call the category μ-bicomplete if every μ-term defines a functor. We provide concrete ex- amples of such categories and explicitly characterize this class of functors for the category of sets and functions. This goal is achieved through par- ity games: we associate to each game an algebraic expression and turn the game into a term of a categorical theory. We show that μ-terms and parity games are equivalent, meaning that they define the same property of being μ-bicomplete. Finally, the interpretation of a parity game in the category of sets is shown to be the set of deterministic winning strategies for a chosen player.
Publié le : 2002-09-04
Classification:  parity games,  induction,  coinduction,  mu-calculi,  [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO],  [MATH.MATH-LO]Mathematics [math]/Logic [math.LO],  [MATH.MATH-CT]Mathematics [math]/Category Theory [math.CT]
@article{Report N°: RR-1281-02,
     author = {Santocanale, Luigi},
     title = {$\mu$-Bicomplete Categories and Parity Games},
     journal = {HAL},
     volume = {2002},
     number = {0},
     year = {2002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/Report N°: RR-1281-02}
}
Santocanale, Luigi. µ-Bicomplete Categories and Parity Games. HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/Report%20N%C2%B0:%20RR-1281-02/