Document Open Access Logo

String Diagrammatic Trace Theory

Authors Matthew Earnshaw , Paweł Sobociński

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.43.pdf
  • Filesize: 0.95 MB
  • 15 pages

Document Identifiers

Author Details

Matthew Earnshaw
  • Department of Software Science, Tallinn University of Technology, Estonia
Paweł Sobociński
  • Department of Software Science, Tallinn University of Technology, Estonia

Funding

Estonian Research Council grant PRG1210 and the European Union under Grant Agreement No. 101087529. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Research Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

Acknowledgements

We thank Chad Nester, Mario Román, and Niels Voorneveld for discussions.

Cite As Get BibTex

Matthew Earnshaw and Paweł Sobociński. String Diagrammatic Trace Theory. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.43

Abstract

We extend the theory of formal languages in monoidal categories to the multi-sorted, symmetric case, and show how this theory permits a graphical treatment of topics in concurrency. In particular, we show that Mazurkiewicz trace languages are precisely symmetric monoidal languages over monoidal distributed alphabets. We introduce symmetric monoidal automata, which define the class of regular symmetric monoidal languages. Furthermore, we prove that Zielonka’s asynchronous automata coincide with symmetric monoidal automata over monoidal distributed alphabets. Finally, we apply the string diagrams for symmetric premonoidal categories to derive serializations of traces.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrency
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Categorical semantics
Keywords
  • symmetric monoidal categories
  • Mazurkiewicz traces
  • asynchronous automata

Metrics

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

References

  1. John C. Baez, Brandon Coya, and Franciscus Rebro. Props in network theory. Theory and Applications of Categories, 33(25):727-783, 2018. Google Scholar
  2. John C Baez, Fabrizio Genovese, Jade Master, and Michael Shulman. Categories of nets. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13. IEEE, 2021. Google Scholar
  3. Guillaume Boisseau and Pawel Sobocinski. String diagrammatic electrical circuit theory. Electronic Proceedings in Theoretical Computer Science, 372:178-191, 2022. Google Scholar
  4. Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. Full abstraction for signal flow graphs. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '15, pages 515-526, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2676726.2676993.
  5. Francis Bossut, Max Dauchet, and Bruno Warin. A Kleene theorem for a class of planar acyclic graphs. Inf. Comput., 117:251-265, March 1995. URL: https://doi.org/10.1006/inco.1995.1043.
  6. Albert Burroni. Higher-dimensional word problems with applications to equational logic. Theoretical Computer Science, 115(1):43-62, 1993. URL: https://doi.org/10.1016/0304-3975(93)90054-W.
  7. M Clerbout, M Latteux, and Y Roos. Semi-commutations. In V Diekert and G Rozenberg, editors, The Book of Traces. World Scientific, 1995. Google Scholar
  8. Bob Coecke, Tobias Fritz, and Robert W. Spekkens. A mathematical theory of resources. Information and Computation, 250:59-86, 2016. Quantum Physics and Logic. URL: https://doi.org/10.1016/j.ic.2016.02.008.
  9. Bob Coecke and Aleks Kissinger. Picturing quantum processes : a first course in quantum theory and diagrammatic reasoning. Cambridge University Press, 2017. Google Scholar
  10. V Diekert and G Rozenberg. The Book of Traces. World Scientific, 1995. URL: https://doi.org/10.1142/2563.
  11. Volker Diekert and Anca Muscholl. On distributed monitoring of asynchronous systems. In Luke Ong and Ruy de Queiroz, editors, Logic, Language, Information and Computation, pages 70-84, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  12. Matthew Earnshaw and Paweł Sobociński. Regular Monoidal Languages. In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), volume 241 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1-44:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2022.44.
  13. Hoogeboom H J and G Rozenberg. Dependence graphs. In V Diekert and G Rozenberg, editors, The Book of Traces. World Scientific, 1995. Google Scholar
  14. Alan Jeffrey. Premonoidal categories and a graphical view of programs. Preprint, 1998. Google Scholar
  15. S. Jesi, G. Pighizzini, and N. Sabadini. Probabilistic asynchronous automata. Mathematical systems theory, 29(1):5-31, February 1996. URL: https://doi.org/10.1007/BF01201811.
  16. André Joyal and Ross Street. The geometry of tensor calculus, I. Advances in Mathematics, 88(1):55-112, 1991. URL: https://doi.org/10.1016/0001-8708(91)90003-P.
  17. C. Krattenthaler. The theory of heaps and the Cartier-Foata monoid. In P. Cartier and D. Foata, editors, Commutation and Rearrangements. European Mathematical Information Service, 2006. Google Scholar
  18. Elena Di Lavore, Giovanni de Felice, and Mario Román. Coinductive streams in monoidal categories, 2022. URL: https://arxiv.org/abs/2212.14494.
  19. Hendrik Maarand and Tarmo Uustalu. Reordering derivatives of trace closures of regular languages. In 30th International Conference on Concurrency Theory (CONCUR 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  20. Saunders MacLane. Categorical algebra. Bulletin of the American Mathematical Society, 71(1):40-106, 1965. Google Scholar
  21. Antoni Mazurkiewicz. Basic notions of trace theory. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, pages 285-363, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg. Google Scholar
  22. José Meseguer and Ugo Montanari. Petri nets are monoids. Information and Computation, 88(2):105-155, 1990. URL: https://doi.org/10.1016/0890-5401(90)90013-8.
  23. Madhavan Mukund. Automata on distributed alphabets. In Modern Applications of Automata Theory, pages 257-288. World Scientific, 2012. URL: https://doi.org/10.1142/9789814271059_0009.
  24. Chad Nester. Concurrent Process Histories and Resource Transducers. Logical Methods in Computer Science, Volume 19, Issue 1, January 2023. URL: https://doi.org/10.46298/lmcs-19(1:7)2023.
  25. Dusko Pavlovic. Monoidal computer I: Basic computability by string diagrams. Information and Computation, 226:94-116, 2013. Special Issue: Information Security as a Resource. URL: https://doi.org/10.1016/j.ic.2013.03.007.
  26. Paolo Perrone. Distribution monad (nlab entry), 2019. , Last accessed 2023-03-13. URL: https://ncatlab.org/nlab/show/distribution+monad.
  27. John Power and Edmund Robinson. Premonoidal categories and notions of computation. Mathematical Structures in Computer Science, 7(5), 1997. URL: https://doi.org/10.1017/S0960129597002375.
  28. Mario Román. Promonads and string diagrams for effectful categories. In ACT '22: Applied Category Theory, Glasgow, United Kingdom, 18 - 22 July, 2022, 2022. URL: https://doi.org/10.48550/arXiv.2205.07664.
  29. P. Selinger. A survey of graphical languages for monoidal categories. In B. Coecke, editor, New Structures for Physics, pages 289-355. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-12821-9_4.
  30. Gérard Xavier Viennot. Heaps of pieces, I : Basic definitions and combinatorial lemmas. In Gilbert Labelle and Pierre Leroux, editors, Combinatoire énumérative, pages 321-350, Berlin, Heidelberg, 1986. Springer Berlin Heidelberg. Google Scholar
  31. R.F.C. Walters. A note on context-free languages. Journal of Pure and Applied Algebra, 62(2):199-203, 1989. URL: https://doi.org/10.1016/0022-4049(89)90151-5.
  32. Wieslaw Zielonka. Notes on finite asynchronous automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 21(2):99-135, 1987. 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 About DROPS Imprint Privacy Contact