Abstract We investigate how various forms of bisimulation can be characterised using the technology of logical relations. The approach taken is that each form of bisimulation corresponds to an algebraic …
Abstract We investigate how various forms of bisimulation can be characterised using the technology of logical relations. The approach taken is that each form of bisimulation corresponds to an algebraic structure derived from a transition system, and the general result is that a relation R between two transition systems on state spaces S and T is a bisimulation if and only if the derived algebraic structures are in the logical relation automatically generated from R . We show that this approach works for the original Park–Milner bisimulation and that it extends to weak bisimulation, and branching and semi-branching bisimulation. The paper concludes with a discussion of probabilistic bisimulation, where the situation is slightly more complex, partly owing to the need to encompass bisimulations that are not just relations.
We investigate how various forms of bisimulation can be characterised using the technology of logical relations. The approach taken is that each form of bisimulation corresponds to an algebraic structure …
We investigate how various forms of bisimulation can be characterised using the technology of logical relations. The approach taken is that each form of bisimulation corresponds to an algebraic structure derived from a transition system, and the general result is that a relation $R$ between two transition systems on state spaces $S$ and $T$ is a bisimulation if and only if the derived algebraic structures are in the logical relation automatically generated from $R$. We show that this approach works for the original Park-Milner bisimulation and that it extends to weak bisimulation, and branching and semi-branching bisimulation. The paper concludes with a discussion of probabilistic bisimulation, where the situation is slightly more complex, partly owing to the need to encompass bisimulations that are not just relations.
Given any symmetric monoidal category C, a small symmetric monoidal category Σ and a strong monoidal functor j:Σ→C, it is shown how to construct C[x:jΣ], a polynomial such category, the …
Given any symmetric monoidal category C, a small symmetric monoidal category Σ and a strong monoidal functor j:Σ→C, it is shown how to construct C[x:jΣ], a polynomial such category, the result of freely adjoining to C a system x of monoidal indeterminates for every object j(w) with w∈Σ satisfying a naturality constraint with the arrows of Σ. As a special case, we show how to construct the free co-affine category (symmetric monoidal category with initial unit) on a given small symmetric monoidal category. It is then shown that all the known categories of "possible worlds" used to treat languages that allow for dynamic creation of "new" variables, locations, or names are in fact instances of this construction and hence have appropriate universality properties.
Based on the monoid classifier, we give an alternative axiomatization of Freyd's paracategories, which can be interpreted in any bicategory of partial maps. Assuming furthermore a free-monoid monad T in …
Based on the monoid classifier, we give an alternative axiomatization of Freyd's paracategories, which can be interpreted in any bicategory of partial maps. Assuming furthermore a free-monoid monad T in our ambient category, and coequalisers satisfying some exactness conditions, we give an abstract envelope construction, putting paramonoids (and paracategories) in the more general context of partial algebras. We introduce for the latter the crucial notion of saturation, which characterises those partial algebras which are isomorphic to the ones obtained from their enveloping algebras. We also set up a factorisation system for partial algebras, via epimorphisms and (monic) Kleene morphisms and relate the latter to saturation.
Given a 2-category $\twocat{K}$ admitting a calculus of bimodules, and a 2-monad T on it compatible with such calculus, we construct a 2-category $\twocat{L}$ with a 2-monad S on it …
Given a 2-category $\twocat{K}$ admitting a calculus of bimodules, and a 2-monad T on it compatible with such calculus, we construct a 2-category $\twocat{L}$ with a 2-monad S on it such that: (1)S has the adjoint-pseudo-algebra property. (2)The 2-categories of pseudo-algebras of S and T are equivalent. Thus, coherent structures (pseudo-T-algebras) are transformed into universally characterised ones (adjoint-pseudo-S-algebras). The 2-category $\twocat{L}$ consists of lax algebras for the pseudo-monad induced by T on the bicategory of bimodules of $\twocat{K}$. We give an intrinsic characterisation of pseudo-S-algebras in terms of representability. Two major consequences of the above transformation are the classifications of lax and strong morphisms, with the attendant coherence result for pseudo-algebras. We apply the theory in the context of internal categories and examine monoidal and monoidal globular categories (including their monoid classifiers) as well as pseudo-functors into $\Cat$.
With a view to further applications, we give a self-contained account of indexed limits for 2-categories, including necessary and sufficient conditions for 2-categorical completeness. Many important 2-categories fail to be …
With a view to further applications, we give a self-contained account of indexed limits for 2-categories, including necessary and sufficient conditions for 2-categorical completeness. Many important 2-categories fail to be complete but do admit a wide class of limits. Accordingly, we introduce a variety of particular 2-categorical limits of practical importance, and show that certain of these suffice for the existence of indexed lax- and pseudo-limits. Other important 2-categories fail to admit even pseudo-limits, but do admit the weaker bilimits; we end by discussing these.
Received by the editors 2004-10-30. Transmitted by Steve Lack, Ross Street and RJ Wood. Reprint published on 2005-04-23. Several typographical errors corrected 2012-05-13. 2000 Mathematics Subject Classification: 18-02, 18D10, 18D20.
Received by the editors 2004-10-30. Transmitted by Steve Lack, Ross Street and RJ Wood. Reprint published on 2005-04-23. Several typographical errors corrected 2012-05-13. 2000 Mathematics Subject Classification: 18-02, 18D10, 18D20.
Any attempt to give “foundations”, for category theory or any domain in mathematics, could have two objectives, of course related. (0.1) Noncontradiction : Namely, to provide a formal frame rich …
Any attempt to give “foundations”, for category theory or any domain in mathematics, could have two objectives, of course related. (0.1) Noncontradiction : Namely, to provide a formal frame rich enough so that all the actual activity in the domain can be carried out within this frame, and consistent, or at least relatively consistent with a well-established and “safe” theory, e.g. Zermelo-Frankel (ZF). (0.2) Adequacy , in the following, nontechnical sense: (i) The basic notions must be simple enough to make transparent the syntactic structures involved. (ii) The translation between the formal language and the usual language must be, or very quickly become, obvious. This implies in particular that the terminology and notations in the formal system should be identical, or very similar, to the current ones. Although this may seem minor, it is in fact very important. (iii) “Foundations” can only be “foundations of a given domain at a given moment”, therefore the frame should be easily adaptable to extensions or generalizations of the domain, and, even better, in view of (i), it should suggest how to find meaningful generalizations. (iv) Sometimes (ii) and (iii) can be incompatible because the current notations are not adapted to a more general situation. A compromise is then necessary. Usually when the tradition is very strong (ii) is predominant, but this causes some incoherence for the notations in the more general case (e.g. the notation f ( x ) for the value of a function f at x obliges one, in category theory, to denote the composition of arrows ( f, g ) → g∘f , and all attempts to change this notation have, so far, failed).
Category theory and related topics of mathematics have been increasingly applied to computer science in recent years. This book contains selected papers from the London Mathematical Society Symposium on the …
Category theory and related topics of mathematics have been increasingly applied to computer science in recent years. This book contains selected papers from the London Mathematical Society Symposium on the subject which was held at the University of Durham. Participants at the conference were leading computer scientists and mathematicians working in the area and this volume reflects the excitement and importance of the meeting. All the papers have been refereed and represent some of the most important and current ideas. Hence this book will be essential to mathematicians and computer scientists working in the applications of category theory.
Milner's action calculus implements abstraction in monoidal categories, so that familiar λ-calculi can be subsumed together with the π-calculus and the Petri nets. Variables are generalised to names , which …
Milner's action calculus implements abstraction in monoidal categories, so that familiar λ-calculi can be subsumed together with the π-calculus and the Petri nets. Variables are generalised to names , which allow only a restricted form of substitution. In the present paper, the well-known categorical semantics of the λ-calculus is generalised to the action calculus. A suitable functional completeness theorem for symmetric monoidal categories is proved: we determine the conditions under which the abstraction is definable. Algebraically, the distinction between the variables and the names boils down to the distinction between the transcendental and the algebraic elements. The former lead to polynomial extensions, like, for example, the ring ℤ[ x ]; the latter lead to algebraic extensions like ℤ[√2] or ℤ[ i ]. Building upon the work of P. Gardner, we introduce action categories , and show that they are related to the static action calculus in exactly the same way as cartesian closed categories are related to the λ-calculus. Natural examples of this structure arise from allegories and cartesian bicategories. On the other hand, the free algebras for any commutative Moggi monad form an action category. The general correspondence of action calculi and Moggi monads will be worked out in a sequel to this work.
The uniformity principle for traced monoidal categories has been introduced as a natural generalization of the uniformity principle (Plotkin’s principle) for fixpoint operators in domain theory. We show that this …
The uniformity principle for traced monoidal categories has been introduced as a natural generalization of the uniformity principle (Plotkin’s principle) for fixpoint operators in domain theory. We show that this notion can be used for constructing new traced monoidal categories from known ones. Some classical examples like the Scott induction principle are shown to be instances of these constructions. We also characterize some specific cases of our constructions as suitable enriched limits.
Abstract Traced monoidal categories are introduced, a structure theorem is proved for them, and an example is provided where the structure theorem has application.
Abstract Traced monoidal categories are introduced, a structure theorem is proved for them, and an example is provided where the structure theorem has application.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
An internal full subcategory of a cartesian closed category <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {A}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, is …
An internal full subcategory of a cartesian closed category <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {A}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, is shown to give rise to a structure on the 2-category <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C a t left-parenthesis script upper A right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mi>a</mml:mi> <mml:mi>t</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">Cat(\mathcal {A})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of categories in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {A}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which introduces the notion of size into the analysis of categories in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {A}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and allows proofs by transcendental arguments. The relationship to the currently popular study of locally internal categories is examined. Internal full subcategories of locally presentable categories (in the sense of Gabriel-Ulmer) are studied in detail. An algorithm is developed for their construction and this is applied to the categories of double categories, triple categories, and so on.
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.