Itegories

Source abstract

Abstract An itegory is a restriction category with a Kleene wand. Cockett, Díaz-Boїls, Gallagher, and Hrubeš briefly introduced Kleene wands to capture iteration in restriction categories arising from complexity theory. The purpose of this paper is to develop in more detail the theory of Kleene wands and itegories. A Kleene wand is a binary operator which takes in two disjoint partial maps, one of type upper X right arrow upper X X → X ${X \to X}$ and the other of type upper X right arrow upper A X → A ${X \to A}$ , and produces a partial map upper X right arrow upper A X → A $X \to A$ . This latter map is interpreted as iterating the endomorphism until it lands in the domain of definition of the second map. In a setting with infinite disjoint joins, there is always a canonical Kleene wand realizing this intuition. The standard categorical interpretation of iteration is via trace operators on coproducts. For extensive restriction categories, we explain in detail how having a Kleene wand is equivalent to this standard interpretation of iteration. This suggests that Kleene wands can be used to replace parametrized iteration and traces in restriction categories which lack coproducts. Further evidence of this is exhibited by providing a matrix construction which embeds an itegory into a traced extensive restriction category. We also consider Kleene wands in classical restriction categories and show how, in this case, a Kleene wand is completely determined by its endomorphism component.