Voir la notice de l'article provenant de la source Numdam
For an arbitrary category, we consider the least class of functors containing 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 examples of such categories and explicitly characterize this class of functors for the category of sets and functions. This goal is achieved through parity 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.
@article{ITA_2002__36_2_195_0,
author = {Santocanale, Luigi},
title = {$\mu $-bicomplete categories and parity games},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {195--227},
publisher = {EDP-Sciences},
volume = {36},
number = {2},
year = {2002},
doi = {10.1051/ita:2002010},
mrnumber = {1948769},
zbl = {1024.18001},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2002010/}
}
TY - JOUR AU - Santocanale, Luigi TI - $\mu $-bicomplete categories and parity games JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2002 SP - 195 EP - 227 VL - 36 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2002010/ DO - 10.1051/ita:2002010 LA - en ID - ITA_2002__36_2_195_0 ER -
%0 Journal Article %A Santocanale, Luigi %T $\mu $-bicomplete categories and parity games %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2002 %P 195-227 %V 36 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2002010/ %R 10.1051/ita:2002010 %G en %F ITA_2002__36_2_195_0
Santocanale, Luigi. $\mu $-bicomplete categories and parity games. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 2, pp. 195-227. doi: 10.1051/ita:2002010
Cité par Sources :