# μ-Bicomplete Categories and Parity Games

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 36, Issue: 2, page 195-227
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topSantocanale, Luigi. "μ-Bicomplete Categories and Parity Games." RAIRO - Theoretical Informatics and Applications 36.2 (2010): 195-227. <http://eudml.org/doc/92697>.

@article{Santocanale2010,

abstract = {
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.
},

author = {Santocanale, Luigi},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Parity games; bicomplete categories; initial algebras; final coalgebras;
inductive and coinductive types.; initial algebra; final coalgebra; bicomplete category; parity game; inductive and coinductive type},

language = {eng},

month = {3},

number = {2},

pages = {195-227},

publisher = {EDP Sciences},

title = {μ-Bicomplete Categories and Parity Games},

url = {http://eudml.org/doc/92697},

volume = {36},

year = {2010},

}

TY - JOUR

AU - Santocanale, Luigi

TI - μ-Bicomplete Categories and Parity Games

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 36

IS - 2

SP - 195

EP - 227

AB -
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.

LA - eng

KW - Parity games; bicomplete categories; initial algebras; final coalgebras;
inductive and coinductive types.; initial algebra; final coalgebra; bicomplete category; parity game; inductive and coinductive type

UR - http://eudml.org/doc/92697

ER -

## References

top- P. Aczel, Non-well-founded sets. Stanford University Center for the Study of Language and Information, Stanford, CA (1988).
- P. Aczel, J. Adámek and J. Velebil, A coalgebraic view of infinite trees and iteration, edited by M.L.A. Corradini and U. Montanari. Elsevier Science Publishers, Electron. Notes in Theoret. Comput. Sci. 44 (2001). Zbl1260.68235
- J. Adámek and V. Koubek, Least fixed point of a functor. J. Comput. System Sci.19 (1979) 163-178. Zbl0423.18007
- J. Adámek and J. Rosický, Locally presentable and accessible categories. Cambridge University Press, Cambridge (1994). Zbl0795.18007
- A. Arnold and D. Niwinski, Rudiments of mu-calculus. Elsevier, North-Holland, Stud. Logic Found. Math. 146 (2001). Zbl0968.03002
- M. Barr, Terminal coalgebras in well-founded set theory. Theoret. Comput. Sci.114 (1993) 299-315. Zbl0779.18004
- S.L. Bloom and Z. Ésik, Iteration theories. Springer-Verlag, Berlin (1993). The equational logic of iterative processes. Zbl0773.03033
- S.L. Bloom, Z. Ésik, A. Labella and E.G. Manes, Iteration 2-theories. Appl. Categ. Structures9 (2001) 173-216. Zbl0981.18005
- J.R.B. Cockett and D. Spencer, Strong categorical datatypes. I, in Category theory 1991 (Montreal, PQ, 1991). Providence, RI, Amer. Math. Soc. (1992) 141-169. Zbl0792.18008
- J.R.B. Cockett and D. Spencer, Strong categorical datatypes. II. A term logic for categorical programming. Theoret. Comput. Sci.139 (1995) 69-113. Zbl0874.68033
- R. Cockett and T. Fukushima, About Charity, Yellow Series Report No. 92/480/18. Department of Computer Science, The University of Calgary (1992).
- E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy (extended abstract), in 32nd Annual Symposium on Foundations of Computer Science. IEEE (1991) 368-377.
- E.A. Emerson, C.S. Jutla and A.P. Sistla, On model checking for the µ-calculus and its fragments. Theoret. Comput. Sci.258 (2001) 491-522. Zbl0973.68120
- Z. Ésik and A. Labella, Equational properties of iteration in algebraically complete categories. Theoret. Comput. Sci.195 (1998) 61-89. Mathematical foundations of computer science, Cracow (1996). Zbl0903.18003
- P. Freyd, Algebraically complete categories, in Category theory (Como, 1990). Springer, Berlin (1991) 95-104. Zbl0815.18005
- E. Giménez, A tutorial on recursive types in Coq. Technical Report 0221, INRIA (1998).
- J.M.E. Hyland, The effective topos, in The L.E.J. Brouwer Centenary Symposium (Noordwijkerhout, 1981). North-Holland, Amsterdam (1982) 165-216.
- A. Joyal, Free bicomplete categories. C. R. Math. Rep. Acad. Sci. Canada17 (1995) 219-224. Zbl0847.18001
- A. Joyal, Free lattices, communication and money games, in Logic and scientific methods (Florence, 1995). Kluwer Acad. Publ., Dordrecht (1997) 29-68.
- G.M. Kelly, Elementary observations on 2-categorical limits. Bull. Austral. Math. Soc.39 (1989) 301-317. Zbl0657.18004
- J. Lambek, A fixpoint theorem for complete categories. Math. Z.103 (1968) 151-161. Zbl0149.26105
- D.J. Lehmann and M.B. Smyth, Algebraic specification of data types: A synthetic approach. Math. Systems Theory14 (1981) 97-139. Zbl0457.68035
- M. Makkai and R. Paré, Accessible categories: The foundations of categorical model theory. American Mathematical Society, Providence, RI (1989). Zbl0703.03042
- R. McNaughton, Infinite games played on finite graphs. Ann. Pure Appl. Logic65 (1993) 149-184. Zbl0798.90151
- A.W. Mostowski, Regular expressions for infinite trees and a standard form of automata, in Computation theory (Zaborów, 1984). Springer, Berlin, Lecture Notes in Comput. Sci. 208 (1985) 157-168.
- D. Niwinski, Equational µ-calculus, in Computation theory (Zaborów, 1984). Springer, Berlin, Lecture Notes in Comput. Sci. 208 (1985) 169-176.
- C. Reutenauer, Ensembles libres de chemins dans un graphe. Bull. Soc. Math. France114 (1986) 135-152. Zbl0616.05043
- J.J.M.M. Rutten, Universal coalgebra: A theory of systems. Theoret. Comput. Sci.249 (2000) 3-80. Zbl0951.68038
- L. Santocanale, The alternation hierarchy for the theory of µ-lattices. Theory Appl. Categ.9 (2002) 166-197. A special volume of articles from the Category Theory 2000 Conference (CT2000).
- L. Santocanale, A calculus of circular proofs and its categorical semantics, in FOSSACS02, Foundations of Software Science and Computation Structures. Springer-Verlag, Lecture Notes Comput. Sci. 2303 (2002) 357-371. Zbl1077.03515
- L. Santocanale, Free µ-lattices. J. Pure Appl. Algebra168 (2002) 227-264. Category theory 1999 (Coimbra). Zbl0990.06004
- A.K. Simpson and G.D. Plotkin, Complete axioms for categorical fixed-point operators, in Proc. of 15th Annual Symposium on Logic in Computer Science (2000) 30-41.
- W. Thomas, Languages, automata, and logic edited by G. Rozenberg and A. Salomaa. Springer-Verlag, New York, Handbook of Formal Language Theory III (1996).
- I. Walukiewicz, Pushdown processes: Games and model-checking. Inform. and Comput.164 (2001) 234-263. FLOC '96 (New Brunswick, NJ). Zbl1003.68072
- W. Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoret. Comput. Sci.200 (1998) 135-183. Zbl0915.68120

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.