Document Open Access Logo

Convolution Products on Double Categories and Categorification of Rule Algebras

Authors Nicolas Behr , Paul-André Melliès , Noam Zeilberger

PDF
Thumbnail PDF

File

LIPIcs.FSCD.2023.17.pdf
  • Filesize: 2.26 MB
  • 20 pages

Document Identifiers

Author Details

Nicolas Behr
  • CNRS, Université Paris Cité, IRIF, France
Paul-André Melliès
  • CNRS, Université Paris Cité, INRIA, France
Noam Zeilberger
  • École Polytechnique, LIX, Palaiseau, France

Cite AsGet BibTex

Nicolas Behr, Paul-André Melliès, and Noam Zeilberger. Convolution Products on Double Categories and Categorification of Rule Algebras. In 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 260, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.FSCD.2023.17

Abstract

Motivated by compositional categorical rewriting theory, we introduce a convolution product over presheaves of double categories which generalizes the usual Day tensor product of presheaves of monoidal categories. One interesting aspect of the construction is that this convolution product is in general only oplax associative. For that reason, we identify several classes of double categories for which the convolution product is not just oplax associative, but fully associative. This includes in particular framed bicategories on the one hand, and double categories of compositional rewriting theories on the other. For the latter, we establish a formula which justifies the view that the convolution product categorifies the rule algebra product.

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
Keywords
  • Categorical rewriting
  • double pushout
  • sesqui-pushout
  • double categories
  • convolution product
  • presheaf categories
  • framed bicategories
  • opfibrations
  • rule algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nicolas Behr. Sesqui-Pushout Rewriting: Concurrency, Associativity and Rule Algebra Framework. In Proceedings of http://gcm2019.imag.fr, volume 309 of EPTCS, pages 23-52, 2019. URL: https://doi.org/10.4204/eptcs.309.2.
  2. Nicolas Behr. Tracelets and tracelet analysis of compositional rewriting systems. In Proceedings of ACT 2019, volume 323 of EPTCS, pages 44-71, 2020. URL: https://doi.org/10.4204/EPTCS.323.4.
  3. Nicolas Behr, Vincent Danos, and Ilias Garnier. Stochastic mechanics of graph rewriting. In Proceedings of LiCS '16. ACM Press, 2016. URL: https://doi.org/10.1145/2933575.2934537.
  4. Nicolas Behr, Russ Harmer, and Jean Krivine. Concurrency theorems for non-linear rewriting theories. In Proceedings of ICGT 2021, volume 12741 of LNCS, pages 3-21. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-78946-6_1.
  5. Nicolas Behr, Russ Harmer, and Jean Krivine. Fundamentals of Compositional Rewriting Theory, 2022. URL: https://doi.org/10.48550/ARXIV.2204.07175.
  6. Nicolas Behr and Joachim Kock. Tracelet Hopf Algebras and Decomposition Spaces (Extended Abstract). In Proceedings of ACT 2021, volume 372 of EPTCS, pages 323-337, 2022. URL: https://doi.org/10.4204/EPTCS.372.23.
  7. Nicolas Behr and Jean Krivine. Compositionality of Rewriting Rules with Conditions. Compositionality, 3, 2021. URL: https://doi.org/10.32408/compositionality-3-2.
  8. Nicolas Behr, Jean Krivine, Jakob L. Andersen, and Daniel Merkle. Rewriting theory for the life sciences: A unifying theory of ctmc semantics. Theoretical Computer Science, 884:68-115, 2021. Google Scholar
  9. Nicolas Behr and Pawel Sobocinski. Rule Algebras for Adhesive Categories (extended journal version). LMCS, Volume 16, Issue 3, 2020. URL: https://doi.org/10.23638/LMCS-16(3:2)2020.
  10. Andrea Corradini et al. Sesqui-Pushout Rewriting. In Graph Transformations, volume 4178 of LNCS, pages 30-45. Springer Berlin Heidelberg, 2006. Google Scholar
  11. Brian Day. On closed categories of functors. In Reports of the Midwest Category Seminar IV, number 137 in Lecture Notes in Mathematics, pages 1-38, Berlin, Heidelberg, New York, 1970. Springer-Verlag. Google Scholar
  12. Y. Diers. Familles universelles de morphismes, volume 145 of Publications de l'U.E.R. mathématiques pures et appliquées. Université des sciences et techniques de Lille I, 1978. Google Scholar
  13. H. Ehrig et al. Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science, 2006. URL: https://doi.org/10.1007/3-540-31188-2.
  14. Niles Johnson and Donald Yau. 2-Dimensional Categories. Oxford University Press, January 2021. URL: https://doi.org/10.1093/oso/9780198871378.001.0001.
  15. Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer New York, 2 edition, 1978. URL: https://doi.org/10.1007/978-1-4757-4721-8.
  16. Tom Leinster. Higher Operads, Higher Categories, volume 298 of London Mathematical Society Lecture Note Series. Cambridge University Press, 2004. Google Scholar
  17. Paolo Perrone and Walter Tholen. Kan extensions are partial colimits. Applied Categorical Structures, 30(4):685-753, 2022. URL: https://doi.org/10.1007/s10485-021-09671-9.
  18. Michael Shulman. Framed bicategories and monoidal fibrations. Theory and Applications of Categories, 20(18):650-738, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact