Search

We curry the elementary arithmetic operations of addition and multiplication to give monotone injections on N, and describe & study the inverse monoids that arise from also considering their generalised inverses. This leads to well-known classic inverse monoids, as well as a novel inverse monoid (the 'arithmetic inverse monoid' A) that generalises these in a natural number-theoretic manner. Based on this, we interpret classic inverse semigroup theoretic concepts arithmetically, and vice versa. Composition and normal forms within A are based on the Chinese remainder theorem, and a minimal generating set corresponds to all prime-order polycyclic monoids. This then gives a close connection between Nivat & Perot's normal forms for polycyclic monoids, mixed-radix counting systems, and p-adic norms & distances., Comment: 21 pages, Updated to correct errors in bibliography

This article studies the categorical setting of Abramsky, Haghverdi, and Scott's untyped linear combinatory algebras, and relates this to more recent work of Abramsky and Heunen on Frobenius algebras in the infinitary setting. The key to this is extensional reflexivity (the property of an object being isomorphic to its own internal hom. $N\cong [N\rightarrow N]$). We characterise extensional reflexivity in compact closed categories, and consider how this may be `strictified' to give monoidally equivalent categories where the isomorphisms exhibiting reflexivity are identity arrows. This results in two-object compact closed categories consisting of a unit object, and a non-unit extensionally reflexive object. We study the endomorphism monoids of such `strictly extensionally reflexive' objects from an algebraic viewpoint. They necessarily contain an interesting monoid that may be thought of as Richard Thompson's iconic group F together with the equally iconic bicyclic monoid of semigroup theory, with non-trivial interactions between the two derived from the Frobenius algebra identity. We claim this as a significant example of the (unitless) Frobenius algebras of Abramsky and Heunen. We then give concrete examples, based on the algebra and category theory behind the Geometry of Interaction program. These are based on the traced monoidal category of partial injections, and reflexive objects in the compact closed category that results from applying the Int or GoI construction. We give compact closed categories, monoidally equivalent to compact closed subcategories of Int(pInj), where this reflexivity is exhibited by identity arrows, and show how the above algebraic structures (Thompson's F, the bicyclic monoid, and Frobenius algebras) arise in a fundamental manner., Comment: 50 pages

The famous 3x + 1 problem of L. Collatz needs no introduction; however, this paper concerns a lesser-known, but similarly unresolved, precursor problem : the Original Collatz Conjecture, or OCC. We demonstrate that the core arithmetic operator from the OCC, when combined with a conjunction of J.-Y. Girard from his Geometry of Interaction system, leads to a realisation of R. Thompson's group F as congruential functions, in the sense of J. Conway. We also give the underlying category theory that accounts for this, and describe the core operator from the OCC as a canonical coherence isomorphism., Comment: 12 pages, 1 figure

We give diagrammatic tools to reason about information flow within encrypted communication. In particular, we are interested in deducing where information flow (communication or otherwise) has taken place, and fully accounting for all possible paths. The core mathematical concept is using a single categorical diagram to model the underlying mathematics, the epistemic knowledge of the participants, and (implicitly) the potential or actual communication between participants. A key part of this is a `correctness' or `consistency' criterion that ensures we accurately & fully account for the distinct routes by which information may come to be known (i.e. communication and / or calculation). We demonstrate how this formalism may be applied to answer questions about communication scenarios where we have the partial information about the participants and their interactions. Similarly, we show how to analyse the consequences of changes to protocols or communications, and to enumerate the distinct orders in which events may have occurred. We use various forms of Diffie-Hellman key exchange as an illustration of these techniques. However, they are entirely general; we illustrate in an appendix how other protocols from non-commutative cryptography may be analysed in the same manner., Comment: Extended version of a presentation at Graphical Models for Security (2020)

This paper is about pregroup models of natural languages, and how they relate to the explicitly categorical use of pregroups in Compositional Distributional Semantics and Natural Language Processing. These categorical interpretations make certain assumptions about the nature of natural languages that, when stated formally, may be seen to impose strong restrictions on pregroup grammars for natural languages. We formalize this as a hypothesis about the form that pregroup models of natural languages must take, and demonstrate by an artificial language example that these restrictions are not imposed by the pregroup axioms themselves. We compare and contrast the artificial language examples with natural languages (using Welsh, a language where the 'noun' type cannot be taken as primitive, as an illustrative example). The hypothesis is simply that there must exist a causal connection, or information flow, between the words of a sentence in a language whose purpose is to communicate information. This is not necessarily the case with formal languages that are simply generated by a series of 'meaning-free' rules. This imposes restrictions on the types of pregroup grammars that we expect to find in natural languages; we formalize this in algebraic, categorical, and graphical terms. We take some preliminary steps in providing conditions that ensure pregroup models satisfy these conjectured properties, and discuss the more general forms this hypothesis may take., Comment: In Proceedings CAPNS 2018, arXiv:1811.02701

We give a categorical description of the treatment of the !() exponential in the Geometry of Interaction system, with particular emphasis on the fact that the GoI interpretation 'forgets types'. We demonstrate that it may be thought of as a fixed-point operation for reversible logic & computation., Comment: 15 pages, 6 Figures

This paper introduces and studies a categorical analogue of the familiar monoid semiring construction. By introducing an axiomatisation of summation that unifies notions of summation from algebraic program semantics with various notions of summation from the theory of analysis, we demonstrate that the monoid semiring construction generalises to cases where both the monoid and the semiring are categories. This construction has many interesting and natural categorical properties, and natural computational interpretations., Comment: 34 pages, 5 diagrams

Starting from the observation that distinct notions of copying have arisen in different categorical fields (logic and computation, contrasted with quantum mechanics) this paper addresses the question of when, or whether, they may coincide. Provided all definitions are strict in the categorical sense, we show that this can never be the case. However, allowing for the defining axioms to be taken up to canonical isomorphism, a close connection between the classical structures of categorical quantum mechanics, and the categorical property of self-similarity familiar from logical and computational models becomes apparent. The required canonical isomorphisms are non-trivial, and mix both typed (multi-object) and untyped (single-object) tensors and structural isomorphisms; we give coherence results that justify this approach. We then give a class of examples where distinct self-similar structures at an object determine distinct matrix representations of arrows, in the same way as classical structures determine matrix representations in Hilbert space. We also give analogues of familiar notions from linear algebra in this setting such as changes of basis, and diagonalisation., Comment: 24 pages,7 diagrams

This paper investigates some issues arising in categorical models of reversible logic and computation. Our claim is that the structural (coherence) isomorphisms of these categorical models, although generally overlooked, have decidedly non-trivial computational content. The theory of categorical coherence is based around reversible structural operations (canonical isomorphisms) that allow for transformations between related, but distinct, mathematical structures. A number of coherence theorems are commonly used to treat these transformations as though they are identity maps, from which point onwards they play no part in computational models. We simply wish to point out that doing so overlooks some significant computational content. We give a single example (taken from an uncountably infinite set of similar examples, and based on structures used in models of reversible logic and computation) of a category whose structural isomorphisms manipulate modulo classes of natural numbers. We demonstrate that the coherence properties that usually allow us to ignore these structural isomorphisms in fact correspond to countably infinite families of non-trivial identities in modular arithmetic. Further, proving the correctness of these equalities without recourse to the theory of categorical coherence appears to be a hard task., Comment: 13 pages, 3 diagrams. Accepted for Reversible Computation 2013

This paper studies questions of coherence and strictification related to self-similarity - the identity $S\cong S\otimes S$ in a (semi-)monoidal category. Based on Saavedra's theory of units, we first demonstrate that strict self-similarity cannot simultaneously occur with strict associativity -- i.e. no monoid may have a strictly associative (semi-)monoidal tensor, although many monoids have a semi-monoidal tensor associative up to isomorphism. We then give a simple coherence result for the arrows exhibiting self-similarity and use this to describe a `strictification procedure' that gives a semi-monoidal equivalence of categories relating strict and non-strict self-similarity, and hence monoid analogues of many categorical properties. Using this, we characterise a large class of diagrams (built from the canonical isomorphisms for the relevant tensors, together with the isomorphisms exhibiting the self-similarity) that are guaranteed to commute., Comment: Significant revisions from previous version: proofs simplified and based on Saavedra units & idempotent splitting, monoidal equivalences made explicit, expository sections significantly revised and shortened, notation and terminology revised and clarified, a clearer criterion for coherence given

The role of types in categorical models of meaning is investigated. A general scheme for how typed models of meaning may be used to compare sentences, regardless of their grammatical structure is described, and a toy example is used as an illustration. Taking as a starting point the question of whether the evaluation of such a type system 'loses information', we consider the parametrized typing associated with connectives from this viewpoint. The answer to this question implies that, within full categorical models of meaning, the objects associated with types must exhibit a simple but subtle categorical property known as self-similarity. We investigate the category theory behind this, with explicit reference to typed systems, and their monoidal closed structure. We then demonstrate close connections between such self-similar structures and dagger Frobenius algebras. In particular, we demonstrate that the categorical structures implied by the polymorphically typed connectives give rise to a (lax unitless) form of the special forms of Frobenius algebras known as classical structures, used heavily in abstract categorical approaches to quantum mechanics., Comment: 37 pages, 4 figures

This paper studies one of the best known quantum algorithms - Shor's factorisation algorithm - via categorical distributivity. A key aim of the paper is to provide a minimal set of categorical requirements for key parts of the algorithm, in order to establish the most general setting in which the required operations may be performed efficiently. We demonstrate that Laplaza's theory of coherence for distributivity provides a purely categorical proof of the operational equivalence of two quantum circuits, with the notable property that one is exponentially more efficient than the other. This equivalence also exists in a wide range of categories. When applied to the category of finite dimensional Hilbert spaces, we recover the usual efficient implementation of the quantum oracles at the heart of both Shor's algorithm and quantum period-finding generally; however, it is also applicable in a much wider range of settings., Comment: 17 pages, 11 Figures

Computational devices combining two or more different parts, one controlling the operation of the other, for example, derive their power from the interaction, in addition to the capabilities of the parts. Non-classical computation has tended to consider only single computational models: neural, analog, quantum, chemical, biological, neglecting to account for the contribution from the experimental controls. In this position paper, we propose a framework suitable for analysing combined computational models, from abstract theory to practical programming tools. Focusing on the simplest example of one system controlled by another through a sequence of operations in which only one system is active at a time, the output from one system becomes the input to the other for the next step, and vice versa. We outline the categorical machinery required for handling diverse computational systems in such combinations, with their interactions explicitly accounted for. Drawing on prior work in refinement and retrenchment, we suggest an appropriate framework for developing programming tools from the categorical framework. We place this work in the context of two contrasting concepts of "efficiency": theoretical comparisons to determine the relative computational power do not always reflect the practical comparison of real resources for a finite-sized computational task, especially when the inputs include (approximations of) real numbers. Finally we outline the limitations of our simple model, and identify some of the extensions that will be required to treat more complex interacting computational systems., Comment: In Proceedings QPL 2011, arXiv:1210.0298

We consider the structures given by repeatedly generalising the definition of finite state automata by symmetry considerations, and constructing analogues of transition monoids at each step. This approach first gives us non-deterministic automata, then (non-deterministic) two-way automata and bounded Turing machines --- that is, Turing machines where the read / write head is unable to move past the end of the input word. In the case of two-way automata, the transition monoids generalise to endomorphism monoids in compact closed categories. These use Girard's resolution formula (from the Geometry of Interaction representation of linear logic) to construct the images of singleton words. In the case of bounded Turing machines, the transition homomorphism generalises to a monoid homomorphism from the natural numbers to a monoid constructed from the union of endomorphism monoids of a compact closed category, together with an appropriate composition. These use Girard's execution formula (also from the Geometry of Interaction representation of linear logic) to construct images of singletons., Comment: 21 pages, submitted