In 2009, Hancock, Pattinson and Ghani gave a coalgebraic characterisation of stream processors $A^\mathbb{N} \to B^\mathbb{N}$ drawing on ideas of Brouwerian constructivism. Their stream processors have an intensional character; in this paper, we give a corresponding coalgebraic characterisation of extensional stream processors, i.e., the set of continuous functions $A^\mathbb{N} \to B^\mathbb{N}$. Our account sites both our result and that of op. cit. within the apparatus of comodels for algebraic effects originating with Power-Shkaravska. Within this apparatus, the distinction between intensional and extensional equivalence for stream processors arises in the same way as the the distinction between bisimulation and trace equivalence for labelled transition systems and probabilistic generative systems.

Abstract It is well established that equational algebraic theories and the monads they generate can be used to encode computational effects. An important insight of Power and Shkaravska is that comodels of an algebraic theory $\mathbb{T}$ – i.e., models in the opposite category $\mathcal{S}\mathrm{et}^{\mathrm{op}}$ – provide a suitable environment for evaluating the computational effects encoded by $\mathbb{T}$ . As already noted by Power and Shkaravska, taking comodels yields a functor from accessible monads to accessible comonads on $\mathcal{S}\mathrm{et}$ . In this paper, we show that this functor is part of an adjunction – the “costructure–cosemantics adjunction” of the title – and undertake a thorough investigation of its properties. We show that, on the one hand, the cosemantics functor takes its image in what we term the presheaf comonads induced by small categories; and that, on the other, costructure takes its image in the presheaf monads induced by small categories. In particular, the cosemantics comonad of an accessible monad will be induced by an explicitly-described category called its behaviour category that encodes the static and dynamic properties of the comodels. Similarly, the costructure monad of an accessible comonad will be induced by a behaviour category encoding static and dynamic properties of the comonad coalgebras. We tie these results together by showing that the costructure–cosemantics adjunction is idempotent, with fixpoints to either side given precisely by the presheaf monads and comonads. Along the way, we illustrate the value of our results with numerous examples drawn from computation and mathematics.

In 2009, Ghani, Hancock and Pattinson gave a coalgebraic characterisation of stream processors A^ℕ → B^ℕ drawing on ideas of Brouwerian constructivism. Their stream processors have an intensional character; in this paper, we give a corresponding coalgebraic characterisation of extensional stream processors, i.e., the set of continuous functions A^ℕ → B^ℕ. Our account sites both our result and that of op. cit. within the apparatus of comodels for algebraic effects originating with Power-Shkaravska.

We give a new account of the correspondence, first established by Nishizawa--Power, between finitary monads and Lawvere theories over an arbitrary locally finitely presentable base. Our account explains this correspondence in terms of enriched category theory: the passage from a finitary monad to the corresponding Lawvere theory is exhibited as an instance of free completion of an enriched category under a class of absolute colimits. This extends work of the first author, who established the result in the special case of finitary monads and Lawvere theories over the category of sets; a novel aspect of the generalisation is its use of enrichment over a bicategory, rather than a monoidal category, in order to capture the monad--theory correspondence over all locally finitely presentable bases simultaneously. Comment: 24 pages

In this article, we give precise mathematical form to the idea of a structure whose data and axioms are faithfully represented by a graphical calculus; some prominent examples are operads, polycategories, properads, and PROPs. Building on the established presentation of such structures as algebras for monads on presheaf categories, we describe a characteristic property of the associated monads—the shapeliness of the title—which says that ‘any two operations of the same shape agree’. An important part of this work is the study of analytic functors between presheaf categories, which are a common generalization of Joyal’s analytic endofunctors on sets and of the parametric right adjoint functors on presheaf categories introduced by Diers and studied by Carboni–Johnstone, Leinster and Weber. Our shapely monads will be found among the analytic endofunctors, and may be characterized as the submonads of a universal analytic monad with ‘exactly one operation of each shape’. In fact, shapeliness also gives a way to define the data and axioms of a structure directly from its graphical calculus, by generating a free shapely monad on the basic operations of the calculus. In this article, we do this for some of the examples listed above; in future work, we intend to use this to obtain canonical notions of denotational model for graphical calculi such as Milner’s bigraphs, Lafont’s interaction nets or Girard’s multiplicative proof nets.

The notion of term graph encodes a refinement of inductively generated syntax in which regard is paid to the the sharing and discard of subterms. Inductively generated syntax has an abstract expression in terms of initial algebras for certain endofunctors on the category of sets, which permits one to go beyond the set-based case, and speak of inductively generated syntax in other settings. In this article, we give a similar abstract expression to the notion of term graph. Aspects of the concrete theory are redeveloped in this setting, and applications beyond the realm of sets discussed.

In this paper we construct new categorical models for the identity types of Martin-Löf type theory, in the categories Top of topological spaces and SSet of simplicial sets. We do so building on earlier work of Awodey and Warren [2009], which has suggested that a suitable environment for the interpretation of identity types should be a category equipped with a weak factorization system in the sense of Bousfield--Quillen. It turns out that this is not quite enough for a sound model, due to some subtle coherence issues concerned with stability under substitution; and so our first task is to introduce a slightly richer structure, which we call a homotopy-theoretic model of identity types , and to prove that this is sufficient for a sound interpretation. Now, although both Top and SSet are categories endowed with a weak factorization system---and indeed, an entire Quillen model structure---exhibiting the additional structure required for a homotopy-theoretic model is quite hard to do. However, the categories we are interested in share a number of common features, and abstracting these leads us to introduce the notion of a path object category . This is a relatively simple axiomatic framework, which is nonetheless sufficiently strong to allow the construction of homotopy-theoretic models. Now by exhibiting suitable path object structures on Top and SSet , we endow those categories with the structure of a homotopy-theoretic model and, in this way, obtain the desired topological and simplicial models of identity types.

We describe a non-extensional variant of Martin-Löf type theory, which we call two-dimensional type theory, and equip it with a sound and complete semantics valued in 2-categories.