2016/10/20 by Luigi Santocanale, Santocanale, Luigi
Computer Science · Mathematics · #Advanced Algebra and Logic #Category Theory (math.CT) #FOS: Computer and information sciences #FOS: Mathematics #Homotopy and Cohomology in Algebraic Topology #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.1610.06393
openalex publication_date 2016/10/20 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
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.