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

Coinductive definitions, such as that of an infinite stream, may often be described by elegant logic programs, but ones for which SLD-refutation is of no value as SLD-derivations fall into infinite loops.Such definitions give rise to questions of lazy corecursive derivations and parallelism, as execution of such logic programs can have both recursive and corecursive features at once.Observational and coalgebraic semantics have been used to study them abstractly.The programming developments have often occurred separately and have usually been implementation-led.Here, we give a coherent semantics-led account of the issues, starting with abstract category theoretic semantics, developing coalgebra to characterize naturally arising trees and proceeding towards implementation of a new dialect, CoALP, of logic programming, characterised by guarded lazy corecursion and parallelism.

Abstract Motivated by the search for a body of mathematical theory to support the semantics of computational effects, we first recall the relationship between Lawvere theories and monads on Set . We generalise that relationship from Set to an arbitrary locally presentable category such as Poset and ω Cpo or functor categories such as [ Inj , Set ] and [ Inj , ω Cpo ]. That involves allowing the arities of Lawvere theories to be extended to being size-restricted objects of the locally presentable category. We develop a body of theory at this level of generality, in particular explaining how the relationship between generalised Lawvere theories and monads extends Gabriel–Ulmer duality.

Generalizing Fiore et al.'s use of the category of finite sets to model untyped Cartesian contexts and Tanaka's use of the category of permutations to model untyped linear contexts, we let S be an arbitrary pseudo-monad on Cat and let S1 model untyped contexts in general: this generality includes contexts for sub-structural logics such as the Logic of Bunched Implications and variants. Given a pseudo-distributive law of S over the (partial) pseudo-monad for free cocompletions, we define a canonical substitution monoidal structure on the category [(S1)op, Set], generalizing substitution monoidal structures for Cartesian and linear contexts and providing a natural substitution structure for Bunched Implications and its variants. We give a concrete description of the substitution monoidal structure. We then give an axiomatic definition of a binding signature, again extending the definitions for Cartesian and linear contexts. We investigate examples in detail, then prove the central result of the paper, yielding initial algebra semantics for binding signatures at the level of generality we propose.

We address the question of how elegantly to combine a number of different structures, such as finite product structure, monoidal structure, and colimiting structure, on a category. Extending work of Marmolejo and Lack, we develop the definition of a pseudo-distributive law between pseudo-monads, and we show how the definition and the main theorems about it may be used to model several such structures simultaneously. Specifically, we address the relationship between pseudo-distributive laws and the lifting of one pseudo-monad to the 2-category of algebras and to the Kleisli bicategory of another. This, for instance, sheds light on the preservation of some structures but not others along the Yoneda embedding. Our leading examples are given by the use of open maps to model bisimulation and by the logic of bunched implications.

Whilst the relationship between initial algebras and monads is well understood, the relationship between final coalgebras and comonads is less well explored. This paper shows that the problem is more subtle than might appear at first glance: final coalgebras can form monads just as easily as comonads, and, dually, initial algebras form both monads and comonads.In developing these theories we strive to provide them with an associated notion of syntax. In the case of initial algebras and monads this corresponds to the standard notion of algebraic theories consisting of signatures and equations: models of such algebraic theories are precisely the algebras of the representing monad. We attempt to emulate this result for the coalgebraic case by first defining a notion of cosignature and coequation and then proving that the models of such coalgebraic presentations are precisely the coalgebras of the representing comonad.

Interferometric synthetic aperture radar (InSAR) imaging is a recently developed geodetic technique capable of measuring ground-surface deformation with centimeter to subcentimeter vertical precision and spatial resolution of tens-of-meter over a relatively large region (/spl sim/10/sup 4/ km/sup 2/). The spatial distribution of surface deformation data, derived from InSAR images, enables the construction of detailed mechanical models to enhance the study of magmatic and tectonic processes associated with volcanoes. This paper summarizes our recent InSAR studies of several Alaska volcanoes, which include Okmok, Akutan, Kiska, Augustine, Westdahl, and Peulik volcanoes.

Article Symmetric monoidal sketches Share on Authors: Martin Hyland Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Mill Lane, Cambridge CB2 1SB, England Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Mill Lane, Cambridge CB2 1SB, EnglandView Profile , John Power Laboratory for the Foundations of Computer Science, University of Edinburgh, King's Buildings, Edinburgh EH9 3JZ, Scotland Laboratory for the Foundations of Computer Science, University of Edinburgh, King's Buildings, Edinburgh EH9 3JZ, ScotlandView Profile Authors Info & Claims PPDP '00: Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programmingSeptember 2000 Pages 280–288https://doi.org/10.1145/351268.351299Online:01 September 2000Publication History 7citation298DownloadsMetricsTotal Citations7Total Downloads298Last 12 Months5Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We d e v elop a notion of equivalence between interpretations of the simply typed -calculus together with an equationally de ned abstract data-type, and we s h o w that two i n terpretations are equivalent if and only if they are linked by a logical relation.We s h o w that our construction generalises from the simply typed -calculus to include the linear -calculus and calculi with additional type and term constructors, such a s those given by s u m t ypes or by a strong monad for modelling phenomena such as partiality or nondeterminism.This is all done in terms of category theoretic structure, usingbrations to model logical relations following Hermida, and adapting Jung and Tiuryn's logical relations of varying arity to provide the completeness results, which form the heart of the work.

In “syntactic control of interference” (POPL, 1978), J.C. Reynolds proposes three design principles intended to constrain the scope of imperative state effects in Algol-like languages. The resulting linguistic framework seems to be a very satisfactory way of combining functional and imperative concepts, having the desirable attributes of both purely functional languages (such as PCF) and simple imperative languages (such as the language of while programs). However, Reynolds points out that the “obvious” syntax for interference control has the unfortunate property that β-reductions do not always preserve typings. Reynolds has subsequently presented a solution to this problem (ICALP, 1989), but it is fairly complicated and requires intersection types in the type system. Here, we present a much simpler solution which does not require intersection types. We first describe a new type system inspired in part by linear logic and verify that reductions preserve typings. We then define a class of “bireflective” models, which provide a categorical analysis of structure underlying the new typing rules; a companion paper “Bireflectivity”, in this volume, exposes wider ramifications of this structure. Finally, we describe a concrete model for an illustrative programming language based on the new type system; this improves on earlier such efforts in that states are not assumed to be structured using locations.

We introduce the notion of higher dimensional multigraph. This notion extends that of multigraph, which underlies multicategories and is essentially equivalent to the notion of context-free grammar. We develop the definition and explain how it gives a semantically coherent category theoretic approach to the notion of higher order context-free grammar. It also gives a conceptual framework in which one can study rewrites, and rewrites of rewrites, etcetera, for proofs of sequent calculus. The definition involves a subtle interaction between geometry and linearly defined syntax; we explore the latter here, outlining the geometric intuition.

We consider a finitely branching transition system as a coalgebra for an endofunctor on the category Set of small sets. A map in that category is a functional bisimulation. So, we study the structure of the category of finitely branching transition systems and functional bisimulations by proving general results about the category H-Coalg of H-coalgebras for an endofunctor H on Set. We give conditions under which H-Coalg is complete, cocomplete, symmetric monoidal closed, regular, and has a subobject classifier.

We study the enrichment of models of axiomatic domain theory. To this end, we introduce a new and broader notion of domain, via, that of complete cuboidal set, that complies with the axiomatic requirements. We show that the category of complete cuboidal sets provides a general notion of enrichment for a wide class of axiomatic domain-theoretic structures.

We introduce the notions of premonoidal category and premonoidal functor, and show how these can be used in the denotational semantics of programming languages. We characterize the semantic definitions of Eugenio Moggi's monads as notions of computation, exhibit a representation theorem for our premonoidal setting in terms of monads, and give a fibrational setting for the structure.

'Action calculi' are a class of action structures with added structure. Each action calculus AC(/spl Kscr/) is determined by a set /spl Kscr/ of controls, equipped with reaction rules; calculi such as Petri nets, the typed /spl lambda/-calculus and the /spl pi/-calculus are obtained by varying /spl Kscr/. This paper defines for each /spl Kscr/ a category CS(/spl Kscr/), characterized by equational axioms, of action structures with added structure; they are called 'control structures' and provide models of the calculus AC(/spl Kscr/), which is initial in the category. The 'surface' of an action is defined; this is an abstract correlate of the syntactic notion of 'free name'. Three equational characterizations of the surface are found to be equivalent. This permits a non-syntactic treatment of the linkage among the components of an interactive system. Finally, control structures and their morphisms offer a means of classifying the variety of dynamic disciplines in models of concurrency, such as the mobility present in the /spl pi/-calculus but absent in other calculi.

A type of higher-order two-dimensional sketch is defined which has models in suitable 2-categories. It has as special cases the ordinary sketches of Ehresmann and certain previously defined generalizations of one-dimensional sketches. These sketches allow the specification of constructions in 2-categories such as weighted limits, as well as higher-order constructions such as exponential objects and subobject classifiers, that cannot be sketched by limits and colimits. These sketches are designed to be the basis of a category-based methodology for the description of functional programming languages, complete with rewrite rules giving the operational semantics, that is independent of the usual specification methods based on formal languages and symbolic logic. A definition of ‘path grammar’, generalizing the usual notion of grammar, is given as a step towards this goal.