SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Monads Need Not Be Endofunctors

2010-01-01
Thorsten Altenkirch , James Chapman , Tarmo Uustalu
View PDF Chat

Monads need not be endofunctors

2015-03-06
Thosten Altenkirch , James Chapman , Tarmo Uustalu
We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We … We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We show that the Kleisli and Eilenberg-Moore constructions carry over to relative monads and are related to relative adjunctions. Under reasonable assumptions, relative monads are monoids in the functor category concerned and extend to monads, giving rise to a coreflection between relative monads and monads. Arrows are also an instance of relative monads.
View PDF Chat

Resumptions, Weak Bisimilarity and Big-Step Semantics for While with Interactive I/O: An Exercise in Mixed Induction-Coinduction

2010-08-11
Keiko Nakata , Tarmo Uustalu
We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, … We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, we define several big-step semantics for While with interactive I/O, based on resumptions and termination-sensitive weak bisimilarity. These require nesting inductive definitions in coinductive definitions, which is interesting both mathematically and from the point-of-view of implementation in a proof assistant. After first defining a basic semantics of statements in terms of resumptions with explicit internal actions (delays), we introduce a semantics in terms of delay-free resumptions that essentially removes finite sequences of delays on the fly from those resumptions that are responsive. Finally, we also look at a semantics in terms of delay-free resumptions supplemented with a silent divergence option. This semantics hinges on decisions between convergence and divergence and is only equivalent to the basic one classically. We have fully formalized our development in Coq.
View PDF Chat

Coproducts of Ideal Monads

2004-10-01
Neil Ghani , Tarmo Uustalu
The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads … The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads does not always exist. Although a rather general construction was given by Kelly [Bull. Austral. Math. Soc. 22 (1980) 1–83], its generality is reflected in its complexity which limits the applicability of this construction. Following our own research [C. Lüth and N. Ghani, Lect. Notes Artif. Intell. 2309 (2002) 18–32], and that of Hyland, Plotkin and Power [IFIP Conf. Proc. 223 (2002) 474–484], we are looking for specific situations when simpler constructions are available. This paper uses fixed points to give a simple construction of the coproduct of two ideal monads.

Generalizing Substitution

2003-10-01
Tarmo Uustalu
It is well known that, given an endofunctor H on a category C , the initial (A+H-)-algebras (if existing), i.e. , the algebras of (wellfounded) H-terms over different variable supplies … It is well known that, given an endofunctor H on a category C , the initial (A+H-)-algebras (if existing), i.e. , the algebras of (wellfounded) H-terms over different variable supplies A, give rise to a monad with substitution as the extension operation (the free monad induced by the functor H). Moss [17] and Aczel, Adámek, Milius and Velebil [12] have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete iterativeness), arises from the inverses of the final (A+H-)-coalgebras (if existing), i.e. , the algebras of non-wellfounded H-terms. We show that, upon an appropriate generalization of the notion of substitution, the same can more generally be said about the initial T'(A,-)-algebras resp. the inverses of the final T'(A,-)-coalgebras for any endobifunctor T' on any category C such that the functors T'(-,X) uniformly carry a monad structure.
View PDF Chat

The Recursion Scheme from the Cofree Recursive Comonad

2011-03-01
Tarmo Uustalu , Varmo Vene
We instantiate the general comonad-based construction of recursion schemes for the initial algebra of a functor F to the cofree recursive comonad on F. Differently from the scheme based on … We instantiate the general comonad-based construction of recursion schemes for the initial algebra of a functor F to the cofree recursive comonad on F. Differently from the scheme based on the cofree comonad on F in a similar fashion, this scheme allows not only recursive calls on elements structurally smaller than the given argument, but also subsidiary recursions. We develop a Mendler formulation of the scheme via a generalized Yoneda lemma for initial algebras involving strong dinaturality and hint a relation to circular proofs à la Cockett, Santocanale.

Codensity Lifting of Monads and its Dual

2018-10-29
Shin-ya Katsumata , Tetsuya Sato , Tarmo Uustalu
We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations … We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations which were not supported by its precursor, categorical TT-lifting. After introducing the codensity lifting, we illustrate some examples of codensity liftings of monads along the fibrations from the category of preorders, topological spaces and extended pseudometric spaces to the category of sets, and also the fibration from the category of binary relations between measurable spaces. We also introduce the dual method called density lifting of comonads. We next study the liftings of algebraic operations to the codensity liftings of monads. We also give a characterisation of the class of liftings of monads along posetal fibrations with fibred small meets as a limit of a certain large diagram. Comment: Extended version of the paper presented at CALCO 2015, accepted for publication in LMCS

When is a container a comonad?

2014-09-03
Danel Ahman , James Chapman , Tarmo Uustalu
Abbott, Altenkirch, Ghani and others have taught us that many parameterized datatypes (set functors) can be usefully analyzed via container representations in terms of a set of shapes and a … Abbott, Altenkirch, Ghani and others have taught us that many parameterized datatypes (set functors) can be usefully analyzed via container representations in terms of a set of shapes and a set of positions in each shape. This paper builds on the observation that datatypes often carry additional structure that containers alone do not account for. We introduce directed containers to capture the common situation where every position in a data-structure determines another data-structure, informally, the sub-data-structure rooted by that position. Some natural examples are non-empty lists and node-labelled trees, and data-structures with a designated position (zippers). While containers denote set functors via a fully-faithful functor, directed containers interpret fully-faithfully into comonads. But more is true: every comonad whose underlying functor is a container is represented by a directed container. In fact, directed containers are the same as containers that are comonads. We also describe some constructions of directed containers. We have formalized our development in the dependently typed programming language Agda.
View PDF Chat

Relating Sequent Calculi for Bi-intuitionistic Propositional Logic

2011-01-26
Luís Pinto , Tarmo Uustalu
Bi-intuitionistic logic is the conservative extension of intuitionistic logic with a connective dual to implication. It is sometimes presented as a symmetric constructive subsystem of classical logic. In this paper, … Bi-intuitionistic logic is the conservative extension of intuitionistic logic with a connective dual to implication. It is sometimes presented as a symmetric constructive subsystem of classical logic. In this paper, we compare three sequent calculi for bi-intuitionistic propositional logic: (1) a basic standard-style sequent calculus that restricts the premises of implication-right and exclusion-left inferences to be single-conclusion resp. single-assumption and is incomplete without the cut rule, (2) the calculus with nested sequents by Gore et al., where a complete class of cuts is encapsulated into special "unnest" rules and (3) a cut-free labelled sequent calculus derived from the Kripke semantics of the logic. We show that these calculi can be translated into each other and discuss the ineliminable cuts of the standard-style sequent calculus.
View PDF Chat

On streams that are finitely red

2012-10-10
Marc Bezem , Keiko Nakata , Tarmo Uustalu
Mixing induction and coinduction, we study alternative definitions of streams being finitely red. We organize our definitions into a hierarchy including also some well-known alternatives in intuitionistic analysis. The hierarchy … Mixing induction and coinduction, we study alternative definitions of streams being finitely red. We organize our definitions into a hierarchy including also some well-known alternatives in intuitionistic analysis. The hierarchy collapses classically, but is intuitionistically of strictly decreasing strength. We characterize the differences in strength in a precise way by weak instances of the Law of Excluded Middle.
View PDF Chat

Coherence for Skew-Monoidal Categories

2014-06-05
Tarmo Uustalu
I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence … I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence has to be formulated differently than in the well-known monoidal case. In my (to my knowledge new) version, it becomes a statement of uniqueness of normalizing rewrites. I present a proof of this coherence theorem and also formalize it fully in the dependently typed programming language Agda.
View PDF Chat

A Hoare logic for the coinductive trace-based big-step semantics of While

2015-02-11
Keiko Nakata , Tarmo Uustalu
In search for a foundational framework for reasoning about observable behavior of programs that may not terminate, we have previously devised a trace-based big-step semantics for While. In this semantics, … In search for a foundational framework for reasoning about observable behavior of programs that may not terminate, we have previously devised a trace-based big-step semantics for While. In this semantics, both traces and evaluation (relating initial states of program runs to traces they produce) are defined coinductively. On terminating runs, this semantics agrees with the standard inductive state-based semantics. Here we present a Hoare logic counterpart of our coinductive trace-based semantics and prove it sound and complete. Our logic subsumes the standard partial-correctness state-based Hoare logic as well as the total-correctness variation: they are embeddable. In the converse direction, projections can be constructed: a derivation of a Hoare triple in our trace-based logic can be translated into a derivation in the state-based logic of a translated, weaker Hoare triple. Since we work with a constructive underlying logic, the range of program properties we can reason about has a fine structure; in particular, we can distinguish between termination and nondivergence, e.g., unbounded classically total search fails to be terminating, but is nonetheless nondivergent. Our meta-theory is entirely constructive as well, and we have formalized it in Coq.
View PDF Chat

Eilenberg-Kelly Reloaded

2020-10-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it … The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it is closed and moreover the adjunction holds internally. We dissect the proof of this theorem and observe that the necessity for a side condition on closedness arises because the standard definition of closed category is left-skew in regards to associativity. We analyze Street's observation that left-skew monoidality is equivalent to left-skew closedness and establish that monoidality is equivalent to closedness unconditionally under an adjusted definition of closedness that requires normal associativity. We also work out a definition of right-skew closedness equivalent to right-skew monoidality. We give examples of each type of structure; in particular, we look at the Kleisli category of a left-strong monad on a left-skew closed category and the Kleisli category of a lax closed monad on a right-skew closed category. We also view skew and normal monoidal and closed categories as special cases of skew and normal promonoidal categories and take a brief look at left-skew prounital-closed categories.

Coalgebraic Update Lenses

2014-10-01
Danel Ahman , Tarmo Uustalu
Lenses are mathematical structures used in the context of bidirectional transformations. In this paper, we introduce update lenses as a refinement of ordinary (asymmetric) lenses in which we distinguish between … Lenses are mathematical structures used in the context of bidirectional transformations. In this paper, we introduce update lenses as a refinement of ordinary (asymmetric) lenses in which we distinguish between views and updates. In addition to the set of views, there is a monoid of updates and an action of the monoid on the set of views. Decoupling updates from views allows for other ways of changing the source than just merging a view into the source. We also consider a yet finer dependently typed version of update lenses. We give a number of characterizations of update lenses in terms of bialgebras and coalgebras, including analogs to O'Connor's coalgebraic and Johnson, Rosebrugh and Wood's algebraic characterizations of ordinary lenses. We consider conversion of views and updates, a tensor product of update lenses and composition of update lenses.

Interaction Laws of Monads and Comonads

2020-05-26
Shin-ya Katsumata , Exequiel Rivas , Tarmo Uustalu
We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of … We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of the monoidal category of functor-functor interaction laws. We show that, for suitable generalizations of the concepts of dual and Sweedler dual, the greatest functor resp. monad interacting with a given functor or comonad is its dual while the greatest comonad interacting with a given monad is its Sweedler dual. We relate monad-comonad interaction laws to stateful runners. We show that functor-functor interaction laws are Chu spaces over the category of endofunctors taken with the Day convolution monoidal structure. Hasegawa's glueing endows the category of these Chu spaces with a monoidal structure whose monoid objects are monad-comonad interaction laws.
View PDF Chat

What Makes a Strong Monad?

2022-06-30
Dylan McDermott , Tarmo Uustalu
Strong monads are important for several applications, in particular, in the denotational semantics of effectful languages, where strength is needed to sequence computations that have free variables. Strength is non-trivial: … Strong monads are important for several applications, in particular, in the denotational semantics of effectful languages, where strength is needed to sequence computations that have free variables. Strength is non-trivial: it can be difficult to determine whether a monad has any strength at all, and monads can be strong in multiple ways. We therefore review some of the most important known facts about strength and prove some new ones. In particular, we present a number of equivalent characterizations of strong functor and strong monad, and give some conditions that guarantee existence or uniqueness of strengths. We look at strength from three different perspectives: actions of a monoidal category V, enrichment over V, and powering over V. We are primarily motivated by semantics of effects, but the results are also useful in other contexts.
View PDF Chat

A Categorical Outlook on Cellular Automata

2010-12-15
Silvio Capobianco , Tarmo Uustalu
In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value … In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value of similar modeling of cellular automata. We identify local behaviors of cellular automata with coKleisli maps of the exponent comonad on the category of uniform spaces and uniformly continuous functions and exploit this equivalence to conclude some standard results about cellular automata as instances of basic category-theoretic generalities. In particular, we recover Ceccherini-Silberstein and Coornaert's version of the Curtis-Hedlund theorem.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2018-12-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on sequent calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subcalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

Proof Theory of Partially Normal Skew Monoidal Categories

2021-01-19
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms … The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms but merely transformations in a particular direction. In previous work, we showed that the free skew monoidal category on a set of generating objects can be concretely presented as a sequent calculus. This calculus enjoys cut elimination and admits focusing, i.e. a subsystem of canonical derivations, which solves the coherence problem for skew monoidal categories. In this paper, we develop sequent calculi for partially normal skew monoidal categories, which are skew monoidal categories with one or more structural laws invertible. Each normality condition leads to additional inference rules and equations on them. We prove cut elimination and we show that the calculi admit focusing. The result is a family of sequent calculi between those of skew monoidal categories and (fully normal) monoidal categories. On the level of derivability, these define 8 weakenings of the (unit,tensor) fragment of intuitionistic non-commutative linear logic.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2021-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
View PDF Chat

Coinductive Big-Step Semantics for Concurrency

2013-12-08
Tarmo Uustalu
In a paper presented at SOS 2010, we developed a framework for big-step semantics for interactive input-output in combination with divergence, based on coinductive and mixed inductive-coinductive notions of resumptions, … In a paper presented at SOS 2010, we developed a framework for big-step semantics for interactive input-output in combination with divergence, based on coinductive and mixed inductive-coinductive notions of resumptions, evaluation and termination-sensitive weak bisimilarity. In contrast to standard inductively defined big-step semantics, this framework handles divergence properly; in particular, runs that produce some observable effects and then diverge, are not "lost". Here we scale this approach for shared-variable concurrency on a simple example language. We develop the metatheory of our semantics in a constructive logic.
View PDF Chat

Directed Containers as Categories

2016-04-01
Danel Ahman , Tarmo Uustalu
Directed containers make explicit the additional structure of those containers whose set functor interpretation carries a comonad structure. The data and laws of a directed container resemble those of a … Directed containers make explicit the additional structure of those containers whose set functor interpretation carries a comonad structure. The data and laws of a directed container resemble those of a monoid, while the data and laws of a directed container morphism those of a monoid morphism in the reverse direction. With some reorganization, a directed container is the same as a small category, but a directed container morphism is opcleavage-like. We draw some conclusions for comonads from this observation, considering in particular basic constructions and concepts like the opposite category and a groupoid.
View PDF Chat

Container Combinatorics: Monads and Lax Monoidal Functors

2017-01-01
Tarmo Uustalu
View PDF Chat

Interaction laws of monads and comonads

2019-01-01
Shin-ya Katsumata , Exequiel Rivas , Tarmo Uustalu
We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of … We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of the monoidal category of functor-functor interaction laws. We show that, for suitable generalizations of the concepts of dual and Sweedler dual, the greatest functor resp. monad interacting with a given functor or comonad is its dual while the greatest comonad interacting with a given monad is its Sweedler dual. We relate monad-comonad interaction laws to stateful runners. We show that functor-functor interaction laws are Chu spaces over the category of endofunctors taken with the Day convolution monoidal structure. Hasegawa's glueing endows the category of these Chu spaces with a monoidal structure whose monoid objects are monad-comonad interaction laws.
View PDF Chat

Proof Theory of Skew Non-Commutative MILL

2022-04-13
Tarmo Uustalu , Niccolò Veltri , Cheng-Syuan Wan
Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent … Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent years, the weaker notion of (left) skew monoidal closed category has been proposed by Ross Street, where the three structural laws of left and right unitality and associativity are not required to be invertible, they are merely natural transformations with a specific orientation. A question arises: is it possible to find a logic which is naturally modelled by skew monoidal closed categories? We answer positively by introducing a cut-free sequent calculus for a skew version of NMILL that is a presentation of the free skew monoidal closed category. We study the proof-theoretic semantics of the sequent calculus by identifying a calculus of derivations in normal form, obtained from an adaptation of Andreoli's focusing technique to the skew setting. The resulting focused sequent calculus peculiarly employs a system of tags for keeping track of new formulae appearing in the antecedent and appropriately reducing non-deterministic choices in proof search. Focusing solves the coherence problem for skew monoidal closed categories by exhibiting an effective procedure for deciding equality of maps in the free such category.
View PDF Chat

Finiteness and rational sequences, constructively

2017-01-01
Tarmo Uustalu , Niccolò Veltri
Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we … Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we literally translate the above definition of rational sequence into the language of type theory, i.e., we construct predicates on possibly infinite sequences expressing the finiteness of the set of suffixes. In type theory, there exist several inequivalent notions of finiteness. We consider two of them, listability and Noetherianness, and show that in the implementation of rational sequences the two notions are interchangeable. Then we introduce the type of lists with backpointers, which is an inductive implementation of rational sequences. Lists with backpointers can be unwound into rational sequences, and rational sequences can be truncated into lists with backpointers. As an example, we see how to convert the fractional representation of a rational number into its decimal representation and vice versa.

Variations on Noetherianness

2016-04-01
Denis Firsov , Tarmo Uustalu , Niccolò Veltri
In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We … In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We want to say that a set is Noetherian, if, when we are shown elements from it one after another, we will sooner or later have seen some element twice. This idea can be made precise in a number of ways. We explore the properties and connections of some of the possible encodings. In particular, we show that certain implementations imply decidable equality while others do not, and we construct counterexamples in the latter case. Additionally, we explore the relation between Noetherianness and other notions of finiteness.
View PDF Chat

Codensity Lifting of Monads and its Dual

2018-01-01
Shin-ya Katsumata , Tetsuya Sato , Tarmo Uustalu
We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations … We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations which were not supported by its precursor, categorical TT-lifting. After introducing the codensity lifting, we illustrate some examples of codensity liftings of monads along the fibrations from the category of preorders, topological spaces and extended pseudometric spaces to the category of sets, and also the fibration from the category of binary relations between measurable spaces. We also introduce the dual method called density lifting of comonads. We next study the liftings of algebraic operations to the codensity liftings of monads. We also give a characterisation of the class of liftings of monads along posetal fibrations with fibred small meets as a limit of a certain large diagram.
View PDF Chat

Deductive Systems and Coherence for Skew Prounital Closed Categories

2021-01-08
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.
View PDF Chat

A Note on Strong Dinaturality, Initial Algebras and Uniform Parameterized Fixpoint Operators.

2010-01-01
Tarmo Uustalu

Deductive systems and coherence for skew prounital closed categories

2020-06-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.

Generating Representative Executions [Extended Abstract]

2017-04-08
Hendrik Maarand , Tarmo Uustalu
Analyzing the behaviour of a concurrent program is made difficult by the number of possible executions. This problem can be alleviated by applying the theory of Mazurkiewicz traces to focus … Analyzing the behaviour of a concurrent program is made difficult by the number of possible executions. This problem can be alleviated by applying the theory of Mazurkiewicz traces to focus only on the canonical representatives of the equivalence classes of the possible executions of the program. This paper presents a generic framework that allows to specify the possible behaviours of the execution environment, and generate all Foata-normal executions of a program, for that environment, by discarding abnormal executions during the generation phase. The key ingredient of Mazurkiewicz trace theory, the dependency relation, is used in the framework in two roles: first, as part of the specification of which executions are allowed at all, and then as part of the normality checking algorithm, which is used to discard the abnormal executions. The framework is instantiated to the relaxed memory models of the SPARC hierarchy.
View PDF Chat

Antifounded Coinduction in Type Theory

2018-01-23
Tarmo Uustalu
Venanzio Capretta, Varmo Vene and I have previously studied antifounded algebras as a a category-theoretic formulation of antifounded coinduction. These are the dual of wellfounded coalgebras, a category theorist's take … Venanzio Capretta, Varmo Vene and I have previously studied antifounded algebras as a a category-theoretic formulation of antifounded coinduction. These are the dual of wellfounded coalgebras, a category theorist's take on wellfounded induction, closely related to the Bove-Capretta method for justifying function definitions by general recursion in type theory. In this talk, we discuss one possible type-theoretic approach to antifounded coinduction.
View PDF Chat

Reordering Derivatives of Trace Closures of Regular Languages (Full Version)

2019-01-01
Hendrik Maarand , Tarmo Uustalu
We provide syntactic derivative-like operations, defined by recursion on regular expressions, in the styles of both Brzozowski and Antimirov, for trace closures of regular languages. Just as the Brzozowski and … We provide syntactic derivative-like operations, defined by recursion on regular expressions, in the styles of both Brzozowski and Antimirov, for trace closures of regular languages. Just as the Brzozowski and Antimirov derivative operations for regular languages, these syntactic reordering derivative operations yield deterministic and nondeterministic automata respectively. But trace closures of regular languages are in general not regular, hence these automata cannot generally be finite. Still, as we show, for star-connected expressions, the Antimirov and Brzozowski automata, suitably quotiented, are finite. We also define a refined version of the Antimirov reordering derivative operation where parts-of-derivatives (states of the automaton) are nonempty lists of regular expressions rather than single regular expressions. We define the uniform scattering rank of a language and show that, for a regexp whose language has finite uniform scattering rank, the truncation of the (generally infinite) refined Antimirov automaton, obtained by removing long states, is finite without any quotienting, but still accepts the trace closure. We also show that star-connected languages have finite uniform scattering rank.

The sequent calculus of skew monoidal categories (extended version)

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger

Structured general corecursion and coinductive graphs [extended abstract]

2012-02-14
Tarmo Uustalu
Bove and Capretta's popular method for justifying function definitions by general recursive equations is based on the observation that any structured general recursion equation defines an inductive subset of the … Bove and Capretta's popular method for justifying function definitions by general recursive equations is based on the observation that any structured general recursion equation defines an inductive subset of the intended domain (the "domain of definedness") for which the equation has a unique solution. To accept the definition, it is hence enough to prove that this subset contains the whole intended domain. This approach works very well for "terminating" definitions. But it fails to account for "productive" definitions, such as typical definitions of stream-valued functions. We argue that such definitions can be treated in a similar spirit, proceeding from a different unique solvability criterion. Any structured recursive equation defines a coinductive relation between the intended domain and intended codomain (the "coinductive graph"). This relation in turn determines a subset of the intended domain and a quotient of the intended codomain with the property that the equation is uniquely solved for the subset and quotient. The equation is therefore guaranteed to have a unique solution for the intended domain and intended codomain whenever the subset is the full set and the quotient is by equality.
View PDF Chat

Sweedler Theory of Monads

2022-01-01
Dylan McDermott , Exequiel Rivas , Tarmo Uustalu
Abstract Monad-comonad interaction laws are a mathematical concept for describing communication protocols between effectful computations and coeffectful environments in the paradigm where notions of effectful computation are modelled by monads … Abstract Monad-comonad interaction laws are a mathematical concept for describing communication protocols between effectful computations and coeffectful environments in the paradigm where notions of effectful computation are modelled by monads and notions of coeffectful environment by comonads. We show that monad-comonad interaction laws are an instance of measuring maps from Sweedler theory for duoidal categories whereby the final interacting comonad for a monad and a residual monad arises as the Sweedler hom and the initial residual monad for a monad and an interacting comonad as the Sweedler copower. We then combine this with a (co)algebraic characterization of monad-comonad interaction laws to derive descriptions of the Sweedler hom and the Sweedler copower in terms of their coalgebras resp. algebras.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context, and the connectives behave like in the standard monoidal sequent calculus except that the left rules may only be applied in stoup position. We prove that this calculus is sound and complete with respect to existence of maps in the free skew monoidal category, and moreover that it captures equality of maps once a suitable equivalence relation is imposed on derivations. We then identify a subsystem of focused derivations and establish that it contains exactly one canonical representative from each equivalence class. This coherence theorem leads directly to simple procedures for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates. Finally, and in the spirit of Lambek's work, we describe the close connection between this proof-theoretic analysis and Bourke and Lack's recent characterization of skew monoidal categories as left representable skew multicategories. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

A Categorical Outlook on Cellular Automata

2010-01-01
Silvio Capobianco , Tarmo Uustalu
In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value … In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value of similar modeling of cellular automata. We identify local behaviors of cellular automata with coKleisli maps of the exponent comonad on the category of uniform spaces and uniformly continuous functions and exploit this equivalence to conclude some standard results about cellular automata as instances of basic category-theoretic generalities. In particular, we recover Ceccherini-Silberstein and Coornaert's version of the Curtis-Hedlund theorem.
View PDF Chat

Canonical Gradings of Monads

2023-07-28
Flavien Breuvart , Dylan McDermott , Tarmo Uustalu
We define a notion of grading of a monoid T in a monoidal category C, relative to a class of morphisms M (which provide a notion of M-subobject). We show … We define a notion of grading of a monoid T in a monoidal category C, relative to a class of morphisms M (which provide a notion of M-subobject). We show that, under reasonable conditions (including that M forms a factorization system), there is a canonical grading of T. Our application is to graded monads and models of computational effects. We demonstrate our results by characterizing the canonical gradings of a number of monads, for which C is endofunctors with composition. We also show that we can obtain canonical grades for algebraic operations.
View PDF Chat

Additive Cellular Automata Graded-Monadically

2023-10-16
Silvio Capobianco , Tarmo Uustalu
Cellular automata are an archetypical comonadic notion of computation in that computation happens in the coKleisli category of a comonad. In this paper, we show that they can also be … Cellular automata are an archetypical comonadic notion of computation in that computation happens in the coKleisli category of a comonad. In this paper, we show that they can also be viewed as graded comonadic—a perspective that turns out to be both more informative and also more basic. We also discuss additive cellular automata to show that they admit both a graded comonadic and a graded monadic view. That these two perspectives are simultaneously available in this special case arises from a graded version of an observation by Kleiner about adjoint comonad-monad pairs.
View PDF Chat

A Unifying Categorical View of Nondeterministic Iteration and Tests

2024-07-11
S. A. Goncharov , Tarmo Uustalu
We study Kleene iteration in the categorical context. A celebrated completeness result by Kozen introduced Kleene algebra (with tests) as a ubiquitous tool for lightweight reasoning about program equivalence, and … We study Kleene iteration in the categorical context. A celebrated completeness result by Kozen introduced Kleene algebra (with tests) as a ubiquitous tool for lightweight reasoning about program equivalence, and yet, numerous variants of it came along afterwards to answer the demand for more refined flavors of semantics, such as stateful, concurrent, exceptional, hybrid, branching time, etc. We detach Kleene iteration from Kleene algebra and analyze it from the categorical perspective. The notion, we arrive at is that of Kleene-iteration category (with coproducts and tests), which we show to be general and robust in the sense of compatibility with programming language features, such as exceptions, store, concurrent behavior, etc. We attest the proposed notion w.r.t. various yardsticks, most importantly, by characterizing the free model as a certain category of (nondeterministic) rational trees.
View PDF Chat

A Unifying Categorical View of Nondeterministic Iteration and Tests

2024-07-11
S. A. Goncharov , Tarmo Uustalu
We study Kleene iteration in the categorical context. A celebrated completeness result by Kozen introduced Kleene algebra (with tests) as a ubiquitous tool for lightweight reasoning about program equivalence, and … We study Kleene iteration in the categorical context. A celebrated completeness result by Kozen introduced Kleene algebra (with tests) as a ubiquitous tool for lightweight reasoning about program equivalence, and yet, numerous variants of it came along afterwards to answer the demand for more refined flavors of semantics, such as stateful, concurrent, exceptional, hybrid, branching time, etc. We detach Kleene iteration from Kleene algebra and analyze it from the categorical perspective. The notion, we arrive at is that of Kleene-iteration category (with coproducts and tests), which we show to be general and robust in the sense of compatibility with programming language features, such as exceptions, store, concurrent behavior, etc. We attest the proposed notion w.r.t. various yardsticks, most importantly, by characterizing the free model as a certain category of (nondeterministic) rational trees.
View PDF Chat

Additive Cellular Automata Graded-Monadically

2023-10-16
Silvio Capobianco , Tarmo Uustalu
Cellular automata are an archetypical comonadic notion of computation in that computation happens in the coKleisli category of a comonad. In this paper, we show that they can also be … Cellular automata are an archetypical comonadic notion of computation in that computation happens in the coKleisli category of a comonad. In this paper, we show that they can also be viewed as graded comonadic—a perspective that turns out to be both more informative and also more basic. We also discuss additive cellular automata to show that they admit both a graded comonadic and a graded monadic view. That these two perspectives are simultaneously available in this special case arises from a graded version of an observation by Kleiner about adjoint comonad-monad pairs.
View PDF Chat

Canonical Gradings of Monads

2023-07-28
Flavien Breuvart , Dylan McDermott , Tarmo Uustalu
We define a notion of grading of a monoid T in a monoidal category C, relative to a class of morphisms M (which provide a notion of M-subobject). We show … We define a notion of grading of a monoid T in a monoidal category C, relative to a class of morphisms M (which provide a notion of M-subobject). We show that, under reasonable conditions (including that M forms a factorization system), there is a canonical grading of T. Our application is to graded monads and models of computational effects. We demonstrate our results by characterizing the canonical gradings of a number of monads, for which C is endofunctors with composition. We also show that we can obtain canonical grades for algebraic operations.
View PDF Chat

What Makes a Strong Monad?

2022-06-30
Dylan McDermott , Tarmo Uustalu
Strong monads are important for several applications, in particular, in the denotational semantics of effectful languages, where strength is needed to sequence computations that have free variables. Strength is non-trivial: … Strong monads are important for several applications, in particular, in the denotational semantics of effectful languages, where strength is needed to sequence computations that have free variables. Strength is non-trivial: it can be difficult to determine whether a monad has any strength at all, and monads can be strong in multiple ways. We therefore review some of the most important known facts about strength and prove some new ones. In particular, we present a number of equivalent characterizations of strong functor and strong monad, and give some conditions that guarantee existence or uniqueness of strengths. We look at strength from three different perspectives: actions of a monoidal category V, enrichment over V, and powering over V. We are primarily motivated by semantics of effects, but the results are also useful in other contexts.
View PDF Chat

Proof Theory of Skew Non-Commutative MILL

2022-04-13
Tarmo Uustalu , Niccolò Veltri , Cheng-Syuan Wan
Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent … Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent years, the weaker notion of (left) skew monoidal closed category has been proposed by Ross Street, where the three structural laws of left and right unitality and associativity are not required to be invertible, they are merely natural transformations with a specific orientation. A question arises: is it possible to find a logic which is naturally modelled by skew monoidal closed categories? We answer positively by introducing a cut-free sequent calculus for a skew version of NMILL that is a presentation of the free skew monoidal closed category. We study the proof-theoretic semantics of the sequent calculus by identifying a calculus of derivations in normal form, obtained from an adaptation of Andreoli's focusing technique to the skew setting. The resulting focused sequent calculus peculiarly employs a system of tags for keeping track of new formulae appearing in the antecedent and appropriately reducing non-deterministic choices in proof search. Focusing solves the coherence problem for skew monoidal closed categories by exhibiting an effective procedure for deciding equality of maps in the free such category.
View PDF Chat

Sweedler Theory of Monads

2022-01-01
Dylan McDermott , Exequiel Rivas , Tarmo Uustalu
Abstract Monad-comonad interaction laws are a mathematical concept for describing communication protocols between effectful computations and coeffectful environments in the paradigm where notions of effectful computation are modelled by monads … Abstract Monad-comonad interaction laws are a mathematical concept for describing communication protocols between effectful computations and coeffectful environments in the paradigm where notions of effectful computation are modelled by monads and notions of coeffectful environment by comonads. We show that monad-comonad interaction laws are an instance of measuring maps from Sweedler theory for duoidal categories whereby the final interacting comonad for a monad and a residual monad arises as the Sweedler hom and the initial residual monad for a monad and an interacting comonad as the Sweedler copower. We then combine this with a (co)algebraic characterization of monad-comonad interaction laws to derive descriptions of the Sweedler hom and the Sweedler copower in terms of their coalgebras resp. algebras.
View PDF Chat

Proof Theory of Partially Normal Skew Monoidal Categories

2021-01-19
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms … The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms but merely transformations in a particular direction. In previous work, we showed that the free skew monoidal category on a set of generating objects can be concretely presented as a sequent calculus. This calculus enjoys cut elimination and admits focusing, i.e. a subsystem of canonical derivations, which solves the coherence problem for skew monoidal categories. In this paper, we develop sequent calculi for partially normal skew monoidal categories, which are skew monoidal categories with one or more structural laws invertible. Each normality condition leads to additional inference rules and equations on them. We prove cut elimination and we show that the calculi admit focusing. The result is a family of sequent calculi between those of skew monoidal categories and (fully normal) monoidal categories. On the level of derivability, these define 8 weakenings of the (unit,tensor) fragment of intuitionistic non-commutative linear logic.
View PDF Chat

Deductive Systems and Coherence for Skew Prounital Closed Categories

2021-01-08
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2021-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
View PDF Chat

Eilenberg-Kelly Reloaded

2020-10-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it … The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it is closed and moreover the adjunction holds internally. We dissect the proof of this theorem and observe that the necessity for a side condition on closedness arises because the standard definition of closed category is left-skew in regards to associativity. We analyze Street's observation that left-skew monoidality is equivalent to left-skew closedness and establish that monoidality is equivalent to closedness unconditionally under an adjusted definition of closedness that requires normal associativity. We also work out a definition of right-skew closedness equivalent to right-skew monoidality. We give examples of each type of structure; in particular, we look at the Kleisli category of a left-strong monad on a left-skew closed category and the Kleisli category of a lax closed monad on a right-skew closed category. We also view skew and normal monoidal and closed categories as special cases of skew and normal promonoidal categories and take a brief look at left-skew prounital-closed categories.

Deductive systems and coherence for skew prounital closed categories

2020-06-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.

Interaction Laws of Monads and Comonads

2020-05-26
Shin-ya Katsumata , Exequiel Rivas , Tarmo Uustalu
We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of … We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of the monoidal category of functor-functor interaction laws. We show that, for suitable generalizations of the concepts of dual and Sweedler dual, the greatest functor resp. monad interacting with a given functor or comonad is its dual while the greatest comonad interacting with a given monad is its Sweedler dual. We relate monad-comonad interaction laws to stateful runners. We show that functor-functor interaction laws are Chu spaces over the category of endofunctors taken with the Day convolution monoidal structure. Hasegawa's glueing endows the category of these Chu spaces with a monoidal structure whose monoid objects are monad-comonad interaction laws.
View PDF Chat

The sequent calculus of skew monoidal categories (extended version)

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger

The Sequent Calculus of Skew Monoidal Categories

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context, and the connectives behave like in the standard monoidal sequent calculus except that the left rules may only be applied in stoup position. We prove that this calculus is sound and complete with respect to existence of maps in the free skew monoidal category, and moreover that it captures equality of maps once a suitable equivalence relation is imposed on derivations. We then identify a subsystem of focused derivations and establish that it contains exactly one canonical representative from each equivalence class. This coherence theorem leads directly to simple procedures for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates. Finally, and in the spirit of Lambek's work, we describe the close connection between this proof-theoretic analysis and Bourke and Lack's recent characterization of skew monoidal categories as left representable skew multicategories. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

Reordering Derivatives of Trace Closures of Regular Languages (Full Version)

2019-01-01
Hendrik Maarand , Tarmo Uustalu
We provide syntactic derivative-like operations, defined by recursion on regular expressions, in the styles of both Brzozowski and Antimirov, for trace closures of regular languages. Just as the Brzozowski and … We provide syntactic derivative-like operations, defined by recursion on regular expressions, in the styles of both Brzozowski and Antimirov, for trace closures of regular languages. Just as the Brzozowski and Antimirov derivative operations for regular languages, these syntactic reordering derivative operations yield deterministic and nondeterministic automata respectively. But trace closures of regular languages are in general not regular, hence these automata cannot generally be finite. Still, as we show, for star-connected expressions, the Antimirov and Brzozowski automata, suitably quotiented, are finite. We also define a refined version of the Antimirov reordering derivative operation where parts-of-derivatives (states of the automaton) are nonempty lists of regular expressions rather than single regular expressions. We define the uniform scattering rank of a language and show that, for a regexp whose language has finite uniform scattering rank, the truncation of the (generally infinite) refined Antimirov automaton, obtained by removing long states, is finite without any quotienting, but still accepts the trace closure. We also show that star-connected languages have finite uniform scattering rank.

Interaction laws of monads and comonads

2019-01-01
Shin-ya Katsumata , Exequiel Rivas , Tarmo Uustalu
We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of … We introduce and study functor-functor and monad-comonad interaction laws as mathematical objects to describe interaction of effectful computations with behaviors of effect-performing machines. Monad-comonad interaction laws are monoid objects of the monoidal category of functor-functor interaction laws. We show that, for suitable generalizations of the concepts of dual and Sweedler dual, the greatest functor resp. monad interacting with a given functor or comonad is its dual while the greatest comonad interacting with a given monad is its Sweedler dual. We relate monad-comonad interaction laws to stateful runners. We show that functor-functor interaction laws are Chu spaces over the category of endofunctors taken with the Day convolution monoidal structure. Hasegawa's glueing endows the category of these Chu spaces with a monoidal structure whose monoid objects are monad-comonad interaction laws.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2018-12-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on sequent calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subcalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

Codensity Lifting of Monads and its Dual

2018-10-29
Shin-ya Katsumata , Tetsuya Sato , Tarmo Uustalu
We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations … We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations which were not supported by its precursor, categorical TT-lifting. After introducing the codensity lifting, we illustrate some examples of codensity liftings of monads along the fibrations from the category of preorders, topological spaces and extended pseudometric spaces to the category of sets, and also the fibration from the category of binary relations between measurable spaces. We also introduce the dual method called density lifting of comonads. We next study the liftings of algebraic operations to the codensity liftings of monads. We also give a characterisation of the class of liftings of monads along posetal fibrations with fibred small meets as a limit of a certain large diagram. Comment: Extended version of the paper presented at CALCO 2015, accepted for publication in LMCS

Antifounded Coinduction in Type Theory

2018-01-23
Tarmo Uustalu
Venanzio Capretta, Varmo Vene and I have previously studied antifounded algebras as a a category-theoretic formulation of antifounded coinduction. These are the dual of wellfounded coalgebras, a category theorist's take … Venanzio Capretta, Varmo Vene and I have previously studied antifounded algebras as a a category-theoretic formulation of antifounded coinduction. These are the dual of wellfounded coalgebras, a category theorist's take on wellfounded induction, closely related to the Bove-Capretta method for justifying function definitions by general recursion in type theory. In this talk, we discuss one possible type-theoretic approach to antifounded coinduction.
View PDF Chat

Codensity Lifting of Monads and its Dual

2018-01-01
Shin-ya Katsumata , Tetsuya Sato , Tarmo Uustalu
We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations … We introduce a method to lift monads on the base category of a fibration to its total category. This method, which we call codensity lifting, is applicable to various fibrations which were not supported by its precursor, categorical TT-lifting. After introducing the codensity lifting, we illustrate some examples of codensity liftings of monads along the fibrations from the category of preorders, topological spaces and extended pseudometric spaces to the category of sets, and also the fibration from the category of binary relations between measurable spaces. We also introduce the dual method called density lifting of comonads. We next study the liftings of algebraic operations to the codensity liftings of monads. We also give a characterisation of the class of liftings of monads along posetal fibrations with fibred small meets as a limit of a certain large diagram.
View PDF Chat

Generating Representative Executions [Extended Abstract]

2017-04-08
Hendrik Maarand , Tarmo Uustalu
Analyzing the behaviour of a concurrent program is made difficult by the number of possible executions. This problem can be alleviated by applying the theory of Mazurkiewicz traces to focus … Analyzing the behaviour of a concurrent program is made difficult by the number of possible executions. This problem can be alleviated by applying the theory of Mazurkiewicz traces to focus only on the canonical representatives of the equivalence classes of the possible executions of the program. This paper presents a generic framework that allows to specify the possible behaviours of the execution environment, and generate all Foata-normal executions of a program, for that environment, by discarding abnormal executions during the generation phase. The key ingredient of Mazurkiewicz trace theory, the dependency relation, is used in the framework in two roles: first, as part of the specification of which executions are allowed at all, and then as part of the normality checking algorithm, which is used to discard the abnormal executions. The framework is instantiated to the relaxed memory models of the SPARC hierarchy.
View PDF Chat

Finiteness and rational sequences, constructively

2017-01-01
Tarmo Uustalu , Niccolò Veltri
Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we … Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we literally translate the above definition of rational sequence into the language of type theory, i.e., we construct predicates on possibly infinite sequences expressing the finiteness of the set of suffixes. In type theory, there exist several inequivalent notions of finiteness. We consider two of them, listability and Noetherianness, and show that in the implementation of rational sequences the two notions are interchangeable. Then we introduce the type of lists with backpointers, which is an inductive implementation of rational sequences. Lists with backpointers can be unwound into rational sequences, and rational sequences can be truncated into lists with backpointers. As an example, we see how to convert the fractional representation of a rational number into its decimal representation and vice versa.

Container Combinatorics: Monads and Lax Monoidal Functors

2017-01-01
Tarmo Uustalu
View PDF Chat

Directed Containers as Categories

2016-04-01
Danel Ahman , Tarmo Uustalu
Directed containers make explicit the additional structure of those containers whose set functor interpretation carries a comonad structure. The data and laws of a directed container resemble those of a … Directed containers make explicit the additional structure of those containers whose set functor interpretation carries a comonad structure. The data and laws of a directed container resemble those of a monoid, while the data and laws of a directed container morphism those of a monoid morphism in the reverse direction. With some reorganization, a directed container is the same as a small category, but a directed container morphism is opcleavage-like. We draw some conclusions for comonads from this observation, considering in particular basic constructions and concepts like the opposite category and a groupoid.
View PDF Chat

Variations on Noetherianness

2016-04-01
Denis Firsov , Tarmo Uustalu , Niccolò Veltri
In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We … In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We want to say that a set is Noetherian, if, when we are shown elements from it one after another, we will sooner or later have seen some element twice. This idea can be made precise in a number of ways. We explore the properties and connections of some of the possible encodings. In particular, we show that certain implementations imply decidable equality while others do not, and we construct counterexamples in the latter case. Additionally, we explore the relation between Noetherianness and other notions of finiteness.
View PDF Chat

Monads need not be endofunctors

2015-03-06
Thosten Altenkirch , James Chapman , Tarmo Uustalu
We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We … We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We show that the Kleisli and Eilenberg-Moore constructions carry over to relative monads and are related to relative adjunctions. Under reasonable assumptions, relative monads are monoids in the functor category concerned and extend to monads, giving rise to a coreflection between relative monads and monads. Arrows are also an instance of relative monads.
View PDF Chat

A Hoare logic for the coinductive trace-based big-step semantics of While

2015-02-11
Keiko Nakata , Tarmo Uustalu
In search for a foundational framework for reasoning about observable behavior of programs that may not terminate, we have previously devised a trace-based big-step semantics for While. In this semantics, … In search for a foundational framework for reasoning about observable behavior of programs that may not terminate, we have previously devised a trace-based big-step semantics for While. In this semantics, both traces and evaluation (relating initial states of program runs to traces they produce) are defined coinductively. On terminating runs, this semantics agrees with the standard inductive state-based semantics. Here we present a Hoare logic counterpart of our coinductive trace-based semantics and prove it sound and complete. Our logic subsumes the standard partial-correctness state-based Hoare logic as well as the total-correctness variation: they are embeddable. In the converse direction, projections can be constructed: a derivation of a Hoare triple in our trace-based logic can be translated into a derivation in the state-based logic of a translated, weaker Hoare triple. Since we work with a constructive underlying logic, the range of program properties we can reason about has a fine structure; in particular, we can distinguish between termination and nondivergence, e.g., unbounded classically total search fails to be terminating, but is nonetheless nondivergent. Our meta-theory is entirely constructive as well, and we have formalized it in Coq.
View PDF Chat

Coalgebraic Update Lenses

2014-10-01
Danel Ahman , Tarmo Uustalu
Lenses are mathematical structures used in the context of bidirectional transformations. In this paper, we introduce update lenses as a refinement of ordinary (asymmetric) lenses in which we distinguish between … Lenses are mathematical structures used in the context of bidirectional transformations. In this paper, we introduce update lenses as a refinement of ordinary (asymmetric) lenses in which we distinguish between views and updates. In addition to the set of views, there is a monoid of updates and an action of the monoid on the set of views. Decoupling updates from views allows for other ways of changing the source than just merging a view into the source. We also consider a yet finer dependently typed version of update lenses. We give a number of characterizations of update lenses in terms of bialgebras and coalgebras, including analogs to O'Connor's coalgebraic and Johnson, Rosebrugh and Wood's algebraic characterizations of ordinary lenses. We consider conversion of views and updates, a tensor product of update lenses and composition of update lenses.

When is a container a comonad?

2014-09-03
Danel Ahman , James Chapman , Tarmo Uustalu
Abbott, Altenkirch, Ghani and others have taught us that many parameterized datatypes (set functors) can be usefully analyzed via container representations in terms of a set of shapes and a … Abbott, Altenkirch, Ghani and others have taught us that many parameterized datatypes (set functors) can be usefully analyzed via container representations in terms of a set of shapes and a set of positions in each shape. This paper builds on the observation that datatypes often carry additional structure that containers alone do not account for. We introduce directed containers to capture the common situation where every position in a data-structure determines another data-structure, informally, the sub-data-structure rooted by that position. Some natural examples are non-empty lists and node-labelled trees, and data-structures with a designated position (zippers). While containers denote set functors via a fully-faithful functor, directed containers interpret fully-faithfully into comonads. But more is true: every comonad whose underlying functor is a container is represented by a directed container. In fact, directed containers are the same as containers that are comonads. We also describe some constructions of directed containers. We have formalized our development in the dependently typed programming language Agda.
View PDF Chat

Coherence for Skew-Monoidal Categories

2014-06-05
Tarmo Uustalu
I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence … I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence has to be formulated differently than in the well-known monoidal case. In my (to my knowledge new) version, it becomes a statement of uniqueness of normalizing rewrites. I present a proof of this coherence theorem and also formalize it fully in the dependently typed programming language Agda.
View PDF Chat

Coinductive Big-Step Semantics for Concurrency

2013-12-08
Tarmo Uustalu
In a paper presented at SOS 2010, we developed a framework for big-step semantics for interactive input-output in combination with divergence, based on coinductive and mixed inductive-coinductive notions of resumptions, … In a paper presented at SOS 2010, we developed a framework for big-step semantics for interactive input-output in combination with divergence, based on coinductive and mixed inductive-coinductive notions of resumptions, evaluation and termination-sensitive weak bisimilarity. In contrast to standard inductively defined big-step semantics, this framework handles divergence properly; in particular, runs that produce some observable effects and then diverge, are not "lost". Here we scale this approach for shared-variable concurrency on a simple example language. We develop the metatheory of our semantics in a constructive logic.
View PDF Chat

On streams that are finitely red

2012-10-10
Marc Bezem , Keiko Nakata , Tarmo Uustalu
Mixing induction and coinduction, we study alternative definitions of streams being finitely red. We organize our definitions into a hierarchy including also some well-known alternatives in intuitionistic analysis. The hierarchy … Mixing induction and coinduction, we study alternative definitions of streams being finitely red. We organize our definitions into a hierarchy including also some well-known alternatives in intuitionistic analysis. The hierarchy collapses classically, but is intuitionistically of strictly decreasing strength. We characterize the differences in strength in a precise way by weak instances of the Law of Excluded Middle.
View PDF Chat

Structured general corecursion and coinductive graphs [extended abstract]

2012-02-14
Tarmo Uustalu
Bove and Capretta's popular method for justifying function definitions by general recursive equations is based on the observation that any structured general recursion equation defines an inductive subset of the … Bove and Capretta's popular method for justifying function definitions by general recursive equations is based on the observation that any structured general recursion equation defines an inductive subset of the intended domain (the "domain of definedness") for which the equation has a unique solution. To accept the definition, it is hence enough to prove that this subset contains the whole intended domain. This approach works very well for "terminating" definitions. But it fails to account for "productive" definitions, such as typical definitions of stream-valued functions. We argue that such definitions can be treated in a similar spirit, proceeding from a different unique solvability criterion. Any structured recursive equation defines a coinductive relation between the intended domain and intended codomain (the "coinductive graph"). This relation in turn determines a subset of the intended domain and a quotient of the intended codomain with the property that the equation is uniquely solved for the subset and quotient. The equation is therefore guaranteed to have a unique solution for the intended domain and intended codomain whenever the subset is the full set and the quotient is by equality.
View PDF Chat

The Recursion Scheme from the Cofree Recursive Comonad

2011-03-01
Tarmo Uustalu , Varmo Vene
We instantiate the general comonad-based construction of recursion schemes for the initial algebra of a functor F to the cofree recursive comonad on F. Differently from the scheme based on … We instantiate the general comonad-based construction of recursion schemes for the initial algebra of a functor F to the cofree recursive comonad on F. Differently from the scheme based on the cofree comonad on F in a similar fashion, this scheme allows not only recursive calls on elements structurally smaller than the given argument, but also subsidiary recursions. We develop a Mendler formulation of the scheme via a generalized Yoneda lemma for initial algebras involving strong dinaturality and hint a relation to circular proofs à la Cockett, Santocanale.

Relating Sequent Calculi for Bi-intuitionistic Propositional Logic

2011-01-26
Luís Pinto , Tarmo Uustalu
Bi-intuitionistic logic is the conservative extension of intuitionistic logic with a connective dual to implication. It is sometimes presented as a symmetric constructive subsystem of classical logic. In this paper, … Bi-intuitionistic logic is the conservative extension of intuitionistic logic with a connective dual to implication. It is sometimes presented as a symmetric constructive subsystem of classical logic. In this paper, we compare three sequent calculi for bi-intuitionistic propositional logic: (1) a basic standard-style sequent calculus that restricts the premises of implication-right and exclusion-left inferences to be single-conclusion resp. single-assumption and is incomplete without the cut rule, (2) the calculus with nested sequents by Gore et al., where a complete class of cuts is encapsulated into special "unnest" rules and (3) a cut-free labelled sequent calculus derived from the Kripke semantics of the logic. We show that these calculi can be translated into each other and discuss the ineliminable cuts of the standard-style sequent calculus.
View PDF Chat

A Categorical Outlook on Cellular Automata

2010-12-15
Silvio Capobianco , Tarmo Uustalu
In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value … In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value of similar modeling of cellular automata. We identify local behaviors of cellular automata with coKleisli maps of the exponent comonad on the category of uniform spaces and uniformly continuous functions and exploit this equivalence to conclude some standard results about cellular automata as instances of basic category-theoretic generalities. In particular, we recover Ceccherini-Silberstein and Coornaert's version of the Curtis-Hedlund theorem.
View PDF Chat

Resumptions, Weak Bisimilarity and Big-Step Semantics for While with Interactive I/O: An Exercise in Mixed Induction-Coinduction

2010-08-11
Keiko Nakata , Tarmo Uustalu
We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, … We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, we define several big-step semantics for While with interactive I/O, based on resumptions and termination-sensitive weak bisimilarity. These require nesting inductive definitions in coinductive definitions, which is interesting both mathematically and from the point-of-view of implementation in a proof assistant. After first defining a basic semantics of statements in terms of resumptions with explicit internal actions (delays), we introduce a semantics in terms of delay-free resumptions that essentially removes finite sequences of delays on the fly from those resumptions that are responsive. Finally, we also look at a semantics in terms of delay-free resumptions supplemented with a silent divergence option. This semantics hinges on decisions between convergence and divergence and is only equivalent to the basic one classically. We have fully formalized our development in Coq.
View PDF Chat

Monads Need Not Be Endofunctors

2010-01-01
Thorsten Altenkirch , James Chapman , Tarmo Uustalu
View PDF Chat

A Note on Strong Dinaturality, Initial Algebras and Uniform Parameterized Fixpoint Operators.

2010-01-01
Tarmo Uustalu

A Categorical Outlook on Cellular Automata

2010-01-01
Silvio Capobianco , Tarmo Uustalu
In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value … In programming language semantics, it has proved to be fruitful to analyze context-dependent notions of computation, e.g., dataflow computation and attribute grammars, using comonads. We explore the viability and value of similar modeling of cellular automata. We identify local behaviors of cellular automata with coKleisli maps of the exponent comonad on the category of uniform spaces and uniformly continuous functions and exploit this equivalence to conclude some standard results about cellular automata as instances of basic category-theoretic generalities. In particular, we recover Ceccherini-Silberstein and Coornaert's version of the Curtis-Hedlund theorem.
View PDF Chat

Coproducts of Ideal Monads

2004-10-01
Neil Ghani , Tarmo Uustalu
The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads … The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads does not always exist. Although a rather general construction was given by Kelly [Bull. Austral. Math. Soc. 22 (1980) 1–83], its generality is reflected in its complexity which limits the applicability of this construction. Following our own research [C. Lüth and N. Ghani, Lect. Notes Artif. Intell. 2309 (2002) 18–32], and that of Hyland, Plotkin and Power [IFIP Conf. Proc. 223 (2002) 474–484], we are looking for specific situations when simpler constructions are available. This paper uses fixed points to give a simple construction of the coproduct of two ideal monads.

Generalizing Substitution

2003-10-01
Tarmo Uustalu
It is well known that, given an endofunctor H on a category C , the initial (A+H-)-algebras (if existing), i.e. , the algebras of (wellfounded) H-terms over different variable supplies … It is well known that, given an endofunctor H on a category C , the initial (A+H-)-algebras (if existing), i.e. , the algebras of (wellfounded) H-terms over different variable supplies A, give rise to a monad with substitution as the extension operation (the free monad induced by the functor H). Moss [17] and Aczel, Adámek, Milius and Velebil [12] have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete iterativeness), arises from the inverses of the final (A+H-)-coalgebras (if existing), i.e. , the algebras of non-wellfounded H-terms. We show that, upon an appropriate generalization of the notion of substitution, the same can more generally be said about the initial T'(A,-)-algebras resp. the inverses of the final T'(A,-)-coalgebras for any endobifunctor T' on any category C such that the functors T'(-,X) uniformly carry a monad structure.
View PDF Chat
Coauthor Papers Together
Niccolò Veltri 11
Noam Zeilberger 8
Shin-ya Katsumata 4
Exequiel Rivas 3
James Chapman 3
Keiko Nakata 3
Danel Ahman 3
Silvio Capobianco 3
Dylan McDermott 3
Tetsuya Sato 2
Hendrik Maarand 2
S. A. Goncharov 1
Marc Bezem 1
Denis Firsov 1
Neil Ghani 1
Cheng-Syuan Wan 1
Thorsten Altenkirch 1
Luís Pinto 1
Varmo Vene 1
Thosten Altenkirch 1
Flavien Breuvart 1

Skew-monoidal categories and bialgebroids

2012-08-10
Kornél Szlachányi
View PDF Chat

Triangulations, orientals, and skew monoidal categories

2014-03-28
Stephen Lack , Ross Street
A concrete model of the free skew-monoidal category Fsk on a single generating object is obtained. The situation is clubbable in the sense of G.M. Kelly, so this allows a … A concrete model of the free skew-monoidal category Fsk on a single generating object is obtained. The situation is clubbable in the sense of G.M. Kelly, so this allows a description of the free skew-monoidal category on any category. As the objects of Fsk are meaningfully bracketed words in the skew unit I and the generating object X, it is necessary to examine bracketings and to find the appropriate kinds of morphisms between them. This leads us to relationships between triangulations of polygons, the Tamari lattice, left and right bracketing functions, and the orientals. A consequence of our description of Fsk is a coherence theorem asserting the existence of a strictly structure-preserving faithful functor from Fsk to the skew-monoidal category of finite non-empty ordinals and first-element-and-order-preserving functions. This in turn provides a complete solution to the word problem for skew monoidal categories.
View PDF Chat

Monads need not be endofunctors

2015-03-06
Thosten Altenkirch , James Chapman , Tarmo Uustalu
We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We … We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We show that the Kleisli and Eilenberg-Moore constructions carry over to relative monads and are related to relative adjunctions. Under reasonable assumptions, relative monads are monoids in the functor category concerned and extend to monads, giving rise to a coreflection between relative monads and monads. Arrows are also an instance of relative monads.
View PDF Chat

Skew monoidales, skew warpings and quantum categories

2012-04-01
Stephen Lack , Ross Street
Kornel Szlachanyi [28] recently used the term skew-monoidal category for a particular laxi ed version of monoidal category. He showed that bialgebroids H with base ring R could be characterized … Kornel Szlachanyi [28] recently used the term skew-monoidal category for a particular laxi ed version of monoidal category. He showed that bialgebroids H with base ring R could be characterized in terms of skew-monoidal structures on the category of one-sided R-modules for which the lax unit was R itself. We de ne skew monoidales (or skew pseudo-monoids) in any monoidal bicategory M . These are skew-monoidal categories when M is Cat. Our main results are presented at the level of monoidal bicategories. However, a consequence is that quantum categories [10] with base comonoid C in a suitably complete braided monoidal category V are precisely skew monoidales in Comod(V ) with unit coming from the counit of C. Quantum groupoids (in the sense of [6] rather than [10]) are those skew monoidales with invertible associativity constraint. In fact, we provide some very general results connecting opmonoidal monads and skew monoidales. We use a lax version of the concept of warping de ned in [3] to modify monoidal structures.

The Catalan simplicial set

2014-12-03
Mitchell Buckley , Richard Garner , Stephen Lack +1 more
The Catalan numbers are well-known to be the answer to many different counting problems, and so there are many different families of sets whose cardinalities are the Catalan numbers. We … The Catalan numbers are well-known to be the answer to many different counting problems, and so there are many different families of sets whose cardinalities are the Catalan numbers. We show how such a family can be given the structure of a simplicial set. We show how the low-dimensional parts of this simplicial set classify, in a precise sense, the structures of monoid and of monoidal category. This involves aspects of combinatorics, algebraic topology, quantum groups, logic, and category theory.
View PDF Chat

Skew-closed categories

2012-10-22
Ross Street

Skew monoidal categories and skew multicategories

2018-03-23
John Bourke , Stephen Lack
View PDF Chat

Skew monoidales, skew warpings and quantum categories

2012-01-01
Stephen Lack , Ross Street
Kornel Szlach\'anyi recently used the term skew-monoidal category for a particular laxified version of monoidal category. He showed that bialgebroids $H$ with base ring $R$ could be characterized in terms … Kornel Szlach\'anyi recently used the term skew-monoidal category for a particular laxified version of monoidal category. He showed that bialgebroids $H$ with base ring $R$ could be characterized in terms of skew-monoidal structures on the category of one-sided $R$-modules for which the lax unit was $R$ itself. We define skew monoidales (or skew pseudo-monoids) in any monoidal bicategory $\mathscr M$. These are skew-monoidal categories when $\mathscr M$ is $\mathrm{Cat}$. Our main results are presented at the level of monoidal bicategories. However, a consequence is that quantum categories in the sense of Day-Street with base comonoid $C$ in a suitably complete braided monoidal category $\mathscr V$ are precisely skew monoidales in $\mathrm{Comod} (\mathscr V)$ with unit coming from the counit of $C$. Quantum groupoids are those skew monoidales with invertible associativity constraint. In fact, we provide some very general results connecting opmonoidal monads and skew monoidales. We use a lax version of the concept of warping defined recently by Booker-Street to modify monoidal structures.
View PDF Chat

On MacLane's conditions for coherence of natural associativities, commutativities, etc.

1964-12-01
G. M. Kelly

Coherence for Skew-Monoidal Categories

2014-06-05
Tarmo Uustalu
I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence … I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence has to be formulated differently than in the well-known monoidal case. In my (to my knowledge new) version, it becomes a statement of uniqueness of normalizing rewrites. I present a proof of this coherence theorem and also formalize it fully in the dependently typed programming language Agda.
View PDF Chat

Free skew monoidal categories

2017-12-20
John Bourke , Stephen Lack
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2018-12-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on sequent calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subcalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

From Comodels to Coalgebras: State and Arrays

2004-12-01
John Power , Olha Shkaravska
We investigate the notion of a comodel of a (countable) Lawvere theory, an evident dual to the notion of model. By taking the forgetful functor from the category of comodels … We investigate the notion of a comodel of a (countable) Lawvere theory, an evident dual to the notion of model. By taking the forgetful functor from the category of comodels to Set, every (countable) Lawvere theory generates a comonad on Set. But while Lawvere theories are equivalent to finitary monads on Set, and that result extends to higher cardinality, no such result holds for comonads, and that is not only for size reasons: it is primarily because, while Set is cartesian closed, Setop is not. So every monad with rank on Set generates a comonad on Set, but not conversely. Our leading example is given by the countable Lawvere theory for global state: its category of comodels is the category of arrays, yielding a precise relationship between global state and arrays. Restricting from arbitrary comonads to those comonads generated by Lawvere theories allows us to study new and interesting constructions, in particular that of tensor product.

Generalizations of the Sweedler Dual

2016-07-30
Hans-E. Porst , Ross Street
View PDF Chat

Coalgebraic Update Lenses

2014-10-01
Danel Ahman , Tarmo Uustalu
Lenses are mathematical structures used in the context of bidirectional transformations. In this paper, we introduce update lenses as a refinement of ordinary (asymmetric) lenses in which we distinguish between … Lenses are mathematical structures used in the context of bidirectional transformations. In this paper, we introduce update lenses as a refinement of ordinary (asymmetric) lenses in which we distinguish between views and updates. In addition to the set of views, there is a monoid of updates and an action of the monoid on the set of views. Decoupling updates from views allows for other ways of changing the source than just merging a view into the source. We also consider a yet finer dependently typed version of update lenses. We give a number of characterizations of update lenses in terms of bialgebras and coalgebras, including analogs to O'Connor's coalgebraic and Johnson, Rosebrugh and Wood's algebraic characterizations of ordinary lenses. We consider conversion of views and updates, a tensor product of update lenses and composition of update lenses.

POLYNOMIALS IN CATEGORIES WITH PULLBACKS

2015-01-01
Mark Weber
The theory developed by Gambino and Kock, of polynomials over a locally cartesian closed categoryE, is generalised forE just having pullbacks. The 2-categorical analogue of the theory of polynomials and … The theory developed by Gambino and Kock, of polynomials over a locally cartesian closed categoryE, is generalised forE just having pullbacks. The 2-categorical analogue of the theory of polynomials and polynomial functors is given, and its rela- tionship with Street's theory of brations within 2-categories is explored. Johnstone's notion of \bagdomain data is adapted to the present framework to make it easier to completely exhibit examples of polynomial monads.

Resumptions, Weak Bisimilarity and Big-Step Semantics for While with Interactive I/O: An Exercise in Mixed Induction-Coinduction

2010-08-11
Keiko Nakata , Tarmo Uustalu
We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, … We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, we define several big-step semantics for While with interactive I/O, based on resumptions and termination-sensitive weak bisimilarity. These require nesting inductive definitions in coinductive definitions, which is interesting both mathematically and from the point-of-view of implementation in a proof assistant. After first defining a basic semantics of statements in terms of resumptions with explicit internal actions (delays), we introduce a semantics in terms of delay-free resumptions that essentially removes finite sequences of delays on the fly from those resumptions that are responsive. Finally, we also look at a semantics in terms of delay-free resumptions supplemented with a silent divergence option. This semantics hinges on decisions between convergence and divergence and is only equivalent to the basic one classically. We have fully formalized our development in Coq.
View PDF Chat

Dualising initial algebras

2003-04-01
Neil Ghani , CHRISTOPH LTH , Federico De Marchi +1 more
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 … 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.

When is a container a comonad?

2014-09-03
Danel Ahman , James Chapman , Tarmo Uustalu
Abbott, Altenkirch, Ghani and others have taught us that many parameterized datatypes (set functors) can be usefully analyzed via container representations in terms of a set of shapes and a … Abbott, Altenkirch, Ghani and others have taught us that many parameterized datatypes (set functors) can be usefully analyzed via container representations in terms of a set of shapes and a set of positions in each shape. This paper builds on the observation that datatypes often carry additional structure that containers alone do not account for. We introduce directed containers to capture the common situation where every position in a data-structure determines another data-structure, informally, the sub-data-structure rooted by that position. Some natural examples are non-empty lists and node-labelled trees, and data-structures with a designated position (zippers). While containers denote set functors via a fully-faithful functor, directed containers interpret fully-faithfully into comonads. But more is true: every comonad whose underlying functor is a container is represented by a directed container. In fact, directed containers are the same as containers that are comonads. We also describe some constructions of directed containers. We have formalized our development in the dependently typed programming language Agda.
View PDF Chat

Coinductive big-step operational semantics

2008-11-09
Xavier Leroy , Hervé Grall
View PDF Chat

Coherence in nonmonoidal closed categories

1977-01-01
Miguel L. Laplaza
A Trionmonoidal closed category is a category with an internal homomorphism functor, left Yoneda natural arrows, unity object and some natural transformations and coherence axioms. The object of this paper … A Trionmonoidal closed category is a category with an internal homomorphism functor, left Yoneda natural arrows, unity object and some natural transformations and coherence axioms. The object of this paper is to give a complete solution of the coherence problem in this structure: we use a cut-elimination theorem as basic tool to prove that the elementary natural transformations are characterized by their graph (roughly speaking the graph is the type of identification imposed by a natural transformation on the arguments of its domain and codomain).

Tensors of Comodels and Models for Operational Semantics

2008-10-01
Gordon Plotkin , John Power
In seeking a unified study of computational effects, one must take account of the coalgebraic structure of state in order to give a general operational semantics agreeing with the standard … In seeking a unified study of computational effects, one must take account of the coalgebraic structure of state in order to give a general operational semantics agreeing with the standard one for state. Axiomatically, one needs a countable Lawvere theory L, a comodel C, typically the final one, and a model M, typically free; one then seeks a tensor C⊗M of the comodel with the model that allows operations to flow between the two. We describe such a tensor implicit in the abstract category theoretic literature, explain its significance for computational effects, and calculate it in leading classes of examples, primarily involving state.
View PDF Chat

General Recursion via Coinductive Types

2005-07-13
Venanzio Capretta
A fertile field of research in theoretical computer science investigates the representation of general recursive functions in intensional type theories. Among the most successful approaches are: the use of wellfounded … A fertile field of research in theoretical computer science investigates the representation of general recursive functions in intensional type theories. Among the most successful approaches are: the use of wellfounded relations, implementation of operational semantics, formalization of domain theory, and inductive definition of domain predicates. Here, a different solution is proposed: exploiting coinductive types to model infinite computations. To every type A we associate a type of partial elements Partial(A), coinductively generated by two constructors: the first, return(a) just returns an element a:A; the second, step(x), adds a computation step to a recursive element x:Partial(A). We show how this simple device is sufficient to formalize all recursive functions between two given types. It allows the definition of fixed points of finitary, that is, continuous, operators. We will compare this approach to different ones from the literature. Finally, we mention that the formalization, with appropriate structural maps, defines a strong monad.
View PDF Chat

Premonoidal categories and notions of computation

1997-10-01
John Power , E. Powell Robinson
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 … 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.

Free Applicative Functors

2014-06-05
Paolo Capriotti , Ambrus Kaposi
Applicative functors are a generalisation of monads. Both allow the expression of effectful computations into an otherwise pure language, like Haskell. Applicative functors are to be preferred to monads when … Applicative functors are a generalisation of monads. Both allow the expression of effectful computations into an otherwise pure language, like Haskell. Applicative functors are to be preferred to monads when the structure of a computation is fixed a priori. That makes it possible to perform certain kinds of static analysis on applicative values. We define a notion of free applicative functor, prove that it satisfies the appropriate laws, and that the construction is left adjoint to a suitable forgetful functor. We show how free applicative functors can be used to implement embedded DSLs which can be statically analysed.
View PDF Chat

Hopf measuring comonoids and enrichment

2017-08-22
Martin Hyland , Ignacio López Franco , Christina Vasilakopoulou
We study the existence of universal measuring comonoids $P(A,B)$ for a pair of monoids $A$, $B$ in a braided monoidal closed category, and the associated enrichment of a category of … We study the existence of universal measuring comonoids $P(A,B)$ for a pair of monoids $A$, $B$ in a braided monoidal closed category, and the associated enrichment of a category of monoids over the monoidal category of comonoids. In symmetric categories, we show that if $A$ is a bimonoid and $B$ is a commutative monoid, then $P(A,B)$ is a bimonoid; in addition, if $A$ is a cocommutative Hopf monoid then $P(A,B)$ always is Hopf. If $A$ is a Hopf monoid, not necessarily cocommutative, then $P(A,B)$ is Hopf if the fundamental theorem of comodules holds; to prove this we give an alternative description of the dualizable $P(A,B)$-comodules and use the theory of Hopf (co)monads. We explore the examples of universal measuring comonoids in vector spaces and graded spaces.
View PDF Chat

Infinite trees and completely iterative theories: a coalgebraic view

2003-05-01
Peter Aczel , Jiřı́ Adámek , Stefan Milius +1 more

A theory of linear typings as flows on 3-valent graphs

2018-06-27
Noam Zeilberger
Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or "maps"), this paper develops an analogy between typing (of lambda terms) and coloring (of … Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or "maps"), this paper develops an analogy between typing (of lambda terms) and coloring (of maps). Our starting point is the classical notion of an abelian group-valued "flow" on an abstract graph (Tutte, 1954). Typing a linear lambda term may be naturally seen as constructing a flow (on an embedded 3-valent graph with boundary) valued in a more general algebraic structure consisting of a preordered set equipped with an "implication" operation and unit satisfying composition, identity, and unit laws. Interesting questions and results from the theory of flows (such as the existence of nowhere-zero flows) may then be re-examined from the standpoint of lambda calculus and logic. For example, we give a characterization of when the local flow relations (across vertices) may be categorically lifted to a global flow relation (across the boundary), proving that this holds just in case the underlying map has the orientation of a lambda term. We also develop a basic theory of rewriting of flows that suggests topological meanings for classical completeness results in combinatory logic, and introduce a polarized notion of flow, which draws connections to the theory of proof-nets in linear logic and to bidirectional typing.
View PDF Chat

Free iterative theories: a coalgebraic view

2003-04-01
Ji � Ad�mek , Stefan Milius , J. Velebil
Every finitary endofunctor of $\Set$ is proved to generate a free iterative theory in the sense of Elgot. This work is based on coalgebras, specifically on parametric corecursion, and the … Every finitary endofunctor of $\Set$ is proved to generate a free iterative theory in the sense of Elgot. This work is based on coalgebras, specifically on parametric corecursion, and the proof is presented for categories more general than just $\Set$.

A sequent calculus for a semi-associative law

2019-02-05
Noam Zeilberger
We introduce a sequent calculus with a simple restriction of Lambek's product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) … We introduce a sequent calculus with a simple restriction of Lambek's product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) induced by a semi-associative law (equivalently, right rotation). We establish a focusing property for this sequent calculus (a strengthening of cut-elimination), which yields the following coherence theorem: every valid entailment in the Tamari order has exactly one focused derivation. We then describe two main applications of the coherence theorem, including: 1. A new proof of the lattice property for the Tamari order, and 2. A new proof of the Tutte-Chapoton formula for the number of intervals in the Tamari lattice $Y_n$. Comment: This article is an extended version of a paper presented at FSCD 2017. [v2: minor rev] arXiv admin note: text overlap with arXiv:1701.02917

Eilenberg-Kelly Reloaded

2020-10-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it … The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it is closed and moreover the adjunction holds internally. We dissect the proof of this theorem and observe that the necessity for a side condition on closedness arises because the standard definition of closed category is left-skew in regards to associativity. We analyze Street's observation that left-skew monoidality is equivalent to left-skew closedness and establish that monoidality is equivalent to closedness unconditionally under an adjusted definition of closedness that requires normal associativity. We also work out a definition of right-skew closedness equivalent to right-skew monoidality. We give examples of each type of structure; in particular, we look at the Kleisli category of a left-strong monad on a left-skew closed category and the Kleisli category of a lax closed monad on a right-skew closed category. We also view skew and normal monoidal and closed categories as special cases of skew and normal promonoidal categories and take a brief look at left-skew prounital-closed categories.

Categories for the Working Mathematician

1971-01-01
Saunders Mac Lane
View PDF Chat

Introduction to extensive and distributive categories

1993-02-01
A. Carboni , Stephen Lack , R. F. C. Walters

Wellfounded Trees and Dependent Polynomial Functors

2004-01-01
Nicola Gambino , Martin Hyland
View PDF Chat

Endomorphisms and automorphisms of the shift dynamical system

1969-12-01
Gustav A. Hedlund

Adjoint functors and triples

1965-09-01
Samuel Eilenberg , John C. Moore
A riple F (F, , ) in ctegory a consists of functor F a nd morphisms la F, F F stisfying some identities (see 2, (T.1)- (T.3)) nlogous to those … A riple F (F, , ) in ctegory a consists of functor F a nd morphisms la F, F F stisfying some identities (see 2, (T.1)- (T.3)) nlogous to those stisfied in monoid.Cotriples re defined dually.It has been recognized by Huber [4] that whenever one hs pir of adoint functors T a , S a (see 1), then the functor TS (with appro- priate morphisms resulting from the adjointness relation) constitutes a triple in nd similarly ST yields cotriple in a.The main objective of this pper is to show that this relation between d- jointness nd triples is in some sense reversible.Given triple Y in a we de- fine new ctegory a nd adoint functors T a a, S a a such that the triple given by TS coincides with .There my be mny adoint pirs which in this wy generate the triple Y, but among those there is a uni- versal one (which therefore is in a sense the "best possible one") nd for this one the functor T is faithful (Theorem 2.2).This construction cn best be illustrated by n example.Let a be the ctegory of modules over a commu- tative ring K nd let A be K-lgebm.The functor F A@ together with morphisms nd resulting from the morphisms K A, h @ A A given by the K-algebra structure of A, yield then a triple Y a.The ctegory a is then precisely the ctegory of A-modules.The general construction of a closely resembles this example.As another example, let a be the category of sets nd let F be the functor which to ech set A ssigns the underlying set of the free group generated by A. There results triple Y in a nd a is the category of groups. Let G(, e, G) be cotriple in category A. It has been recognized by Godement [3] and Huber [4], that the iterates G of G together with face and degeneracy morphisms G + G , G G + defined using e and yield a simplicial structure which can be used to define homology and cohomology.Now if Y is a triple in a, then one has an adjoint pair T" aa, S and therefore one has an associated cotriple G in .This in turn yields a simplicial complex for every object in a , thus paving the way for homology and cohomology in ar.In 4 we show that under suitable
View PDF Chat

Higher Operads, Higher Categories

2004-07-22
Tom Leinster
Higher-dimensional category theory is the study of n-categories, operads, braided monoidal categories, and other such exotic structures. It draws its inspiration from areas as diverse as topology, quantum algebra, mathematical … Higher-dimensional category theory is the study of n-categories, operads, braided monoidal categories, and other such exotic structures. It draws its inspiration from areas as diverse as topology, quantum algebra, mathematical physics, logic, and theoretical computer science. The heart of this book is the language of generalized operads. This is as natural and transparent a language for higher category theory as the language of sheaves is for algebraic geometry, or vector spaces for linear algebra. It is introduced carefully, then used to give simple descriptions of a variety of higher categorical structures. In particular, one possible definition of n-category is discussed in detail, and some common aspects of other possible definitions are established. This is the first book on the subject and lays its foundations. It will appeal to both graduate students and established researchers who wish to become acquainted with this modern branch of mathematics.
View PDF Chat

Algebraic theories, monads, and arities

2011-01-01
Charles Grellois
Monads are of interest both in semantics and in higher dimensional algebra. It turns out that the idea behind usual notion finitary monads (whose values on all sets can be … Monads are of interest both in semantics and in higher dimensional algebra. It turns out that the idea behind usual notion finitary monads (whose values on all sets can be computed from their values on finite sets) extends to a more general class of monads called monads with arities, so that not only algebraic theories can be computed from a proper set of arities, but also more general structures like n-categories, the computing process being realized using Kan extensions. This Master thesis compiles the required material in order to understand this question of arities and reconstruction of monads, and tries to give some examples of relevant interest from both semantics and higher category theory. A discussion on the promising field of operads is then provided as appendix.

TOPOSES, TRIPLES AND THEORIES (Grundlehren der mathematischen Wissenschaften 278)

1986-01-01
Peter Johnstone
By M. Barr and C. Wells: pp. 345. DM.138.-. (Springer-Verlag, 1985.) By M. Barr and C. Wells: pp. 345. DM.138.-. (Springer-Verlag, 1985.)

Hopf monoids in varieties

2018-04-17
Hans-E. Porst

Parametric corecursion

2001-06-01
Lawrence S. Moss

Handling Algebraic Effects

2013-12-17
Gordon Plotkin , Matija Pretnar
Algebraic effects are computational effects that can be represented by an equational theory whose operations produce the effects at hand. The free model of this theory induces the expected computational … Algebraic effects are computational effects that can be represented by an equational theory whose operations produce the effects at hand. The free model of this theory induces the expected computational monad for the corresponding effect. Algebraic effects include exceptions, state, nondeterminism, interactive input/output, and time, and their combinations. Exception handling, however, has so far received no algebraic treatment. We present such a treatment, in which each handler yields a model of the theory for exceptions, and each handling construct yields the homomorphism induced by the universal property of the free model. We further generalise exception handlers to arbitrary algebraic effects. The resulting programming construct includes many previously unrelated examples from both theory and practice, including relabelling and restriction in Milner's CCS, timeout, rollback, and stream redirection.
View PDF Chat

Polynomial functors and polynomial monads

2012-09-06
Nicola Gambino , Joachim Kock
We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. … We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. We show that the free monad on a polynomial endofunctor is polynomial. The relationship with operads and other related notions is explored.
View PDF Chat

Sur le nombre d'intervalles dans les treillis de Tamari

2006-01-01
Frédéric Chapoton
We enumerate the intervals in the Tamari lattices. For this, we introduce an inductive description of the intervals. Then a notion of "new interval" is defined and these are also … We enumerate the intervals in the Tamari lattices. For this, we introduce an inductive description of the intervals. Then a notion of "new interval" is defined and these are also enumerated. A a side result, the inverse of two special series is computed in a group of tree-indexed series.
View PDF Chat

Monads Need Not Be Endofunctors

2010-01-01
Thorsten Altenkirch , James Chapman , Tarmo Uustalu
View PDF Chat

Monad transformers as monoid transformers

2010-09-23
Mauro Jaskelioff , Eugenio Moggi
View PDF Chat

Coproducts of Ideal Monads

2004-10-01
Neil Ghani , Tarmo Uustalu
The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads … The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads does not always exist. Although a rather general construction was given by Kelly [Bull. Austral. Math. Soc. 22 (1980) 1–83], its generality is reflected in its complexity which limits the applicability of this construction. Following our own research [C. Lüth and N. Ghani, Lect. Notes Artif. Intell. 2309 (2002) 18–32], and that of Hyland, Plotkin and Power [IFIP Conf. Proc. 223 (2002) 474–484], we are looking for specific situations when simpler constructions are available. This paper uses fixed points to give a simple construction of the coproduct of two ideal monads.

Ramsey's Theorem and the Pigeonhole Principle in Intuitionistic Mathematics

1993-04-01
Wim Veldman , Marc Bezem
At first sight, the argument which F. P. Ramsey gave for (the infinite case of) his famous theorem from 1927, is hopelessly unconstructive. If suitably reformulated, the theorem is true … At first sight, the argument which F. P. Ramsey gave for (the infinite case of) his famous theorem from 1927, is hopelessly unconstructive. If suitably reformulated, the theorem is true intuitionistically as well as classically: we offer a proof which should convince both the classical and the intuitionistic reader.
View PDF Chat

Linear usage of state

2014-03-25
Rasmus Ejlers Møgelberg , Sam Staton
We investigate the phenomenon that "every monad is a linear state monad". We do this by studying a fully-complete state-passing translation from an impure call-by-value language to a new linear … We investigate the phenomenon that "every monad is a linear state monad". We do this by studying a fully-complete state-passing translation from an impure call-by-value language to a new linear type theory: the enriched call-by-value calculus. The results are not specific to store, but can be applied to any computational effect expressible using algebraic operations, even to effects that are not usually thought of as stateful. There is a bijective correspondence between generic effects in the source language and state access operations in the enriched call-by-value calculus. From the perspective of categorical models, the enriched call-by-value calculus suggests a refinement of the traditional Kleisli models of effectful call-by-value languages. The new models can be understood as enriched adjunctions.
View PDF Chat

Coequalizers and free triples

1970-01-01
Michael Barr