Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-10T20:35:35.450Z Has data issue: false hasContentIssue false
  • English
  • Français

A categorical analogue of the monoid semiring construction

Published online by Cambridge University Press:  09 October 2012

PETER HINES
PETER HINES*
Affiliation:
Department of Computer Science, University of York, York, United Kingdom Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 23 , Issue 1 , February 2013 , pp. 55 - 94
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S., Haghverdi, E. and Scott, P. (2002) Geometry of interaction and linear combinatory algebras. Mathematical Structures in Computer Science 12 (5)625–665.CrossRefGoogle Scholar
Abramsky, S. (2005) Abstract Scalars, Loops, and Free Traced and Strongly Compact Closed Categories. Springer-Verlag Lecture Notes in Computer Science 3629 1–29.CrossRefGoogle Scholar
Bahamonde, A. (1985) Tensor Product of Partially-Additive Monoids. Semigroup Forum 32 31–53.CrossRefGoogle Scholar
Day, M. (1973) Normed Linear Spaces (Third edition), Springer-Verlag.CrossRefGoogle Scholar
Deutsch, D., Ekert, A. and Lupacchini, R. (1999) Machines, Logic and Quantum Physics. Available at arXiv:math.HO/9911150 v1.Google Scholar
Haghverdi, E. (2000) A categorical approach to linear logic, geometry of proofs and full completeness, Ph.D. Thesis, University of Ottawa.Google Scholar
Haghverdi, E. and Scott, P. (2006) A categorical model for the Geometry of Interaction. Theoretical Computer Science 350 (2)252–274.CrossRefGoogle Scholar
Gelfand, I. (1938) Abstrakte Funktionen und lineare Operatoren. Recueil Math'ematique [Mat. Sbornik] N.S. 4 (46) volume 2 235–286.Google Scholar
Golan, J. (1999) Power Algebras Over Semirings: With Applications in Mathematics and Computer Science, Mathematics and Its Applications 488, Springer-Verlag.CrossRefGoogle Scholar
Hille, E. (1982) Analytic Function Theory, Volume 1 (Second edition), AMS Chelsea publishing.Google Scholar
Hines, P. (2008a) Machine Semantics. Theoretical Computer Science 409 (1)1–23.CrossRefGoogle Scholar
Hines, P. (2008b) Machine Semantics: from Causality to Computational Models. International Journal of Unconventional Computation 4 (3)249–272.Google Scholar
Hines, P. (2010) Quantum Circuit Oracles for Abstract Machine Computations. Theoretical Computer Science 411 1501–1520.CrossRefGoogle Scholar
Hines, P. and Scott, P. (2012) Categorical Traces from Single-Photon Linear Optics. In: Abramsky, S. and Mislove, M. (eds.) Mathematical Foundations of Information Flow. AMS Proceedings of Symposia in Applied Mathematics 71 89–124.CrossRefGoogle Scholar
Hobson, E. W. (1957) The Theory of Functions of a Real Variable and the Theory of Fourier's Series, Volume 1 (Second edition), Dover Publications.Google Scholar
Kadets, V. and Kadets, M. (1991) Rearrangements of Series in Banach Spaces, American Mathematical Society.CrossRefGoogle Scholar
Kelly, G. M. (1982) Basic Concepts of Enriched Category Theory, LMS Lecture notes 64, Cambridge University Press. (Reprinted in Kelly (2005)).Google Scholar
Kelly, G. M. (2005) Basic Concepts of Enriched Category Theory, Reprints in Theory and Applications of Categories 10.Google Scholar
McArthur, C. (1961) A note on Subseries Convergence. Proceedings of the American Mathematical Society 12 (4)540–545.CrossRefGoogle Scholar
Manes, E. and Arbib, M. (1986) Algebraic Approaches to Program Semantics, Springer-Verlag.CrossRefGoogle Scholar
Manes, E. and Benson, D. (1985) The inverse Semigroup of a Sum-Ordered Semiring. Semigroup Forum 31 129–152.CrossRefGoogle Scholar
Lahiri, B. K. and Das, P. (2002) Subseries in Banach spaces. Mathematica Slovaca 52 (3)361–368.Google Scholar
Laplaza, M. L. (1977) Coherence in Nonmonoidal Closed Categories. Transactions of the American Mathematical Society 230 293–311.CrossRefGoogle Scholar
Nielsen, M. and Chuang, I. (2000) Quantum Computation and Quantum Information, Cambridge University Press.Google Scholar
Orlicz, W. (1933) Über unbedingte Konvergenz in Functionenraumen I. Studia Mathematica 4 33–37.CrossRefGoogle Scholar
Swartz, C. (1992) Iterated series and the Hellinger-Toeplitz theorem. Publicacions Matemàtiques 36 167–173.CrossRefGoogle Scholar
Selinger, P. (2004) Towards a quantum programming language. Mathematical Structures in Computer Science 14 (4)527–586.CrossRefGoogle Scholar
Shor, P. (1999) Polynomial time algorithms for prime factorisation and discrete logarithms on a quantum computer. SIAM review 41 303–332.CrossRefGoogle Scholar
Steinberger, M. (1993) Algebra, Prindle, Weber and Schmidt. (Updated version (2006) available online at http://math.albany.edu/~mark/algebra.pdf.)Google Scholar
Titchmarsh, E. C. (1983) The Theory of Functions (Second edition), Oxford University Press.Google Scholar
Thorpe, B. (1968) On the equivalence of certain notions of bounded variation. Journal of the London Mathematical Society 43 247–252.CrossRefGoogle Scholar