Laboratory for compositional systems and methods
TalTech priority area
Research classification (Frascati)
Head of the research group
Research group member
Doctoral students
Keyword
compositionality
open systems
applied category theory
programming languages
trustworthy software
diagrammatic reasoning
string diagrams
logic in computer science
relational methods
quantum computing
Overview
The group's goal is to study compositional techniques in the context of models of computation, understood broadly. Compositionality means that syntactic descriptions for (open) systems are designed to be compatible with their semantics. While the examples motivating the research come from a broad section of scientific disciplines (logic, control theory, formal language theory, control theory, business processes, game theory, economics, machine learning), we have identified common principles for reasoning about open systems, guided by category theory. These including a semantic universe based on relations rather than functions, and the use of the diagrammatic syntax of string diagrams. String diagrams provide an intuitive calculus for computations via diagrammatic reasoning, and fine-grained control over resources, which is important for faithful descriptions of open systems. Our big questions/challenges are 1) design a next generation of programming/specification languages that will be more suited for compositional (and therefore, more trustworthy and reliable) descriptions of systems, 2) use compositionality to improve the analysis of systems, including the design of new techniques and algorithms, and 3) design and implement tools for working with string diagrams, fast-tracking the passage from theory to practice.
Important results
Hadzihasanovic, A.; Kessler, D. (2023). Higher-dimensional subdiagram matching. 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 26 - 29 June, 2023, Boston, USA. ACM, 13 pp. DOI: 10.1109/LICS56636.2023.10175726
Related projects
Related department
- Di Lavore, E., De Felice, G., Roman Garcia, M. Monoidal streams for dataflow programming // 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022, Haifa, 2 August 2022 - 5 August 2022. New York : ACM, 2022. art. 3533365, p. 1-14 : ill.
https://doi.org/10.1145/3531130.3533365 - Bonchi, F., Gadducci, F., Kissinger, A., Sobocinski, P.M., Zanasi, F. String diagram rewrite theory I : rewriting with Frobenius structure // Journal of the ACM (2022) vol. 69, 2, art. 14.
https://doi.org/10.1145/3502719 - Loregian, F. (Co)end Calculus. London : Cambridge University Press, 2021. 330 p. (London Mathematical Society Lecture Note Series ; 468).
https://doi.org/10.1017/9781108778657 - Hadzihasanovic, A. The smash product of monoidal theories // 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 29 June-2 July 2021, Rome, Italy, virtual : proceedings. : IEEE, 2021. art. 9470575, 13 p.
https://doi.org/10.1109/LICS52264.2021.9470575 - Di Liberti, I., Loregian, F., Nester, C.M., Sobocinski, P.M. Functorial semantics for partial theories // Proceedings of the ACM on Programming Languages (2021) vol. 5, no. POPL, art. 57, 28 p. : ill.
https://doi.org/10.1145/3434338 - Behr, N., Sobocinski, P.M. Rule algebras for adhesive categories // Logical methods in computer science (2020) vol. 16, 3, p. 2:1−2:38.
https://doi.org/10.23638/LMCS-16(3:2)2020 - Roman Garcia, M. Open diagrams via Coend calculus // Proceedings of the 3rd Annual International Applied Category Theory Conference 2020. Cambridge, Massachusetts : Open Publishing Association, 2021. p. 65-78 : ill. (Electronic Proceedings in Theoretical Computer Science (EPTCS) ; 333).
https://doi.org/10.4204/EPTCS.333.5 - Boisseau, G., Sobocinski, P.M. String diagrammatic electrical circuit theory // arXiv. New York : Cornell University, 2022. p. 178-191 : ill. (Electronic proceedings in theoretical computer science, EPTCS ; 372).
https://doi.org/10.4204/EPTCS.372.13 https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?ACT2021.13 - Bonchi, F., Sobocinski, P.M., Zanasi, F. A survey of Compositional signal flow theory // Advancing Research in Information and Communication Technology : IFIP's Exciting First 60+ Years, Views from the Technical Committees and Working Groups. Cham : Springer Nature, 2021. p. 29–56. (IFIP Advances in Information and Communication Technology ; Volume 600).
https://doi.org/10.1007/978-3-030-81701-5_2 - Bonchi, F., Gadducci, F., Kissinger, A., Sobocinski, P.M., Zanasi, F. String diagram rewrite theory III : confluence with and without Frobenius // Mathematical structures in computer science (2022) vol. 7, special issue 7, p. 829-869.
https://doi.org/10.1017/S0960129522000123 - Nester, C.M. The structure of concurrent process histories // Coordination Models and Languages : 23rd IFIP WG 6.1 International Conference, COORDINATION 2021, Held as Part of the 16th International Federated Conference on Distributed Computing Techniques, DisCoTec 2021, Valletta, Malta, June 14-18, 2021 : proceedings. Cham : Springer, 2021. p. 209−224. (Lecture notes in computer science ; 12717).
https://doi.org/10.1007/978-3-030-78142-2_13 - Bonchi, F., Gadducci, F., Kissinger, A., Sobocinski, P., Zanasi, F. String diagram rewrite theory II : rewriting with symmetric monoidal structure // Mathematical structures in computer science (2022) Volume 32, Issue 4, p. 511 - 541.
https://doi.org/10.1017/S0960129522000317 - Pietarinen, A-V., Bellucci, F., Bobrova, A., Haydon, N., Shafiei, M. The Blot // Diagrammatic representation and inference : 11th International Conference, Diagrams 2020, Tallinn, Estonia, August 24–28, 2020 : proceedings. Cham : Springer, 2020. p. 225-238 : ill. (Lecture notes in computer science ; 12169, Lecture notes in artificial intelligence ; 12169).
https://doi.org/10.1007/978-3-030-54249-8_18 - Nester, C.M. A foundation for ledger structures // 2nd International Conference on Blockchain Economics, Security and Protocols : Tokenomics 2020, October 26–27, 2020, Toulouse, France. Dagstuhl : Dagstuhl Publishing, 2021. art. 7, p. 7:1–7:31. (Open Access Series in Informatics (OASIcs) ; 82).
https://doi.org/10.4230/OASIcs.Tokenomics.2020.7 - Di Lavore, E., Gianola, A., Roman Garcia, M., Sabadini, N., Sobocinski, P.M. A canonical algebra of open transition systems // Formal aspects of component software : 17th International Conference, FACS 2021, Virtual Event, October 28-29, 2021 : proceedings. Cham : Springer Nature, 2021. p. 63-81. (Lecture notes in computer science ; 13077).
https://doi.org/10.1007/978-3-030-90636-8_4 - Haydon, N.J., Sobocinski, P.M. Compositional diagrammatic first-order logic // Diagrammatic representation and inference : 11th International Conference, Diagrams 2020, Tallinn, Estonia, August 24–28, 2020 : proceedings. Cham : Springer, 2020. p. 402-418. (Lecture notes in computer science ; 12169, Lecture notes in artificial intelligence ; 12169).
https://doi.org/10.1007/978-3-030-54249-8_32 - Di Lavore, E., Hedges, J., Sobocinski, P.M. Compositional modelling of network games // 29th EACSL Annual Conference on Computer Science Logic : CSL 2021, January 25–28, 2021, Ljubljana, Slovenia (Virtual Conference). Wadern : Dagstuhl Publishing, 2021. art. 30, p. 30:1–30:24 : ill. (Leibniz international proceedings in informatics (LIPIcs) ; 183).
https://doi.org/10.4230/LIPIcs.CSL.2021.30 - Genovese, F., Herold, J., Loregian, F., Palombi, D. A categorical semantics for hierarchical Petri Nets // Proceedings Twelfth International Workshop on Graph Computational Models, Online, 22nd June 2021. : Open Publishing Association, 2021. p. 51−68. (Electronic proceedings in theoretical computer science ; 350).
https://doi.org/10.48550/arXiv.2102.00096 - Genovese, F., Loregian, F., Palombi, D. Nets with mana : a framework for chemical reaction modelling // Graph Transformation : 14th International Conference, ICGT 2021, Held as Part of STAF 2021, Virtual Event, June 24-25, 2021 : proceedings. Cham : Springer Nature, 2021. p. 185−202. (Lecture notes in computer science ; 12741).
https://doi.org/10.1007/978-3-030-78946-6_10 - Paixao, J., Sobocinski, P.M. Calculational proofs in relational graphical linear algebra // Formal Methods: Foundations and Applications : 23rd Brazilian Symposium, SBMF 2020, Ouro Preto, Brazil, November 25-27, 2020 : proceedings. Cham : Springer, 2020. p. 83-100. (Lecture notes in computer science ; 12475).
https://doi.org/10.1007/978-3-030-63882-5_6 - Nester, C.M. Situated transition systems // arXiv. New York : Cornell University, 2022. p. 103-115. (Electronic proceedings in theoretical computer science, EPTCS ; 372).
https://doi.org/10.4204/EPTCS.372.8 - Bonchi, F., Santamaria, A., Seeber, J., Sobocinski, P.M. On doctrines and Cartesian bicategories // CALCO 2021 : 9th International Conference on Algebra and Coalgebra in Computer Science, Aug 31 - Sep 3, 2021, Salzburg, Austria : proceedings. Dagstuhl : Dagstuhl Publishing, 2021. p. 10:1−10:7. (Leibniz international proceedings in informatics (LIPIcs) ; 211).
https://doi.org/10.4230/LIPIcs.CALCO.2021.10 - Bonchi, F., Piedeleu, R., Sobocinski, P.M., Zanasi, F. Contextual equivalence for signal flow graphs // Foundations of Software Science and Computation Structures : 23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25-30, 2020 : proceedings. Cham : Springer, 2020. p. 77-96. (Lecture notes in computer science ; 12077).
https://doi.org/10.1007/978-3-030-45231-5_5 - Paixao, J., Rufino, L., Sobocinski, P. M. High-level axioms for graphical linear algebra // Science of computer programming (2022) vol. 218, art. 102791 ; 26 p.
https://doi.org/10.1016/j.scico.2022.102791 - Earnshaw, M., Sobocinski, P.M. Regular monoidal languages // Leibniz International Proceedings in Informatics, LIPIcs. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. p. 44:1-44:14. (Leibniz International Proceedings in Informatics (LIPIcs) ; 241).
https://doi.org/10.4230/LIPIcs.MFCS.2022.44 - Felice, G. de, Di Lavore, E., Roman Garcia, M., Toumi, A. Functorial language games for question answering // Proceedings of the 3rd Annual International Applied Category Theory Conference 2020. : Cornell University, 2021. p. 311–321. (Electronic Proceedings in Theoretical Computer Science (EPTCS) ; 333).
https://doi.org/10.4204/EPTCS.333.21 - Loregian, F., Virili, S. Triangulated factorization systems and t-structures // Journal of algebra (2020) vol. 550, p. 219-241.
https://doi.org/10.1016/j.jalgebra.2019.12.021 - Bonchi, F., Piedeleu, R., Sobocinski, P. M., Zanasi, F. Bialgebraic foundations for the operational semantics of string diagrams // Information and computation (2021) vol. 281, art. 104767, 22 p.
https://doi.org/10.1016/j.ic.2021.104767 - Bonchi, F., Di Giorgio, A., Sobocinski, P.M. Diagrammatic polyhedral algebra // 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Dagstuhl, Germany : Schloss Dagstuhl, 2021. p. 40:1-40:18. (Leibniz international proceedings in informatics (LIPIcs) ; 213).
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.40 - Loregian, F., de Oliveira Santos, T. Coends of higher arity // Applied categorical structures (2022) vol. 30, 1, p. 173-221.
https://doi.org/10.1007/s10485-021-09653-x - Haydon, N., Pietarinen, A-V. Residuation in existential graphs // Diagrammatic Representation and Inference : 12th International Conference, Diagrams 2021, Virtual, September 28–30, 2021 : proceedings. Cham : Springer, 2021. p. 229−237. (Lecture notes in computer science ; 12909).
https://doi.org/10.1007/978-3-030-86062-2_21 - Nester, C. M. A variety theorem for relational universal algebra // Relational and Algebraic Methods in Computer Science : 19th International Conference, RAMiCS 2021, Marseille, France, November 2–5, 2021 : proceedings. Cham : Springer Nature, 2021. p. 362–377. (Lecture Notes in Computer Science, 13027).
https://doi.org/10.1007/978-3-030-88701-8_22 - Genovese, F., Loregian, F., Palombi, D. A Categorical semantics for bounded Petri Nets // Proceedings of the 4th Annual International Applied Category Theory Conference 2021 [ACT 2021] : Cambridge, United Kingdom, 12-16 July 2021. : Open Publishing Association, 2021. 15 p.
https://doi.org/10.48550/arXiv.2101.09100 - Firsov, D., Laur, S., Zhuchko, E. Unsatisfiability of comparison-based non-malleability for commitments // Theoretical Aspects of Computing - ICTAC 2022 : 19th International Colloquium, Tbilisi, Georgia, September 27-30, 2022 : proceedings. Cham : Springer Nature, 2022. p. 188–194. (Lecture notes in computer science ; 13572).
https://doi.org/10.1007/978-3-031-17715-6_13 - Dea, S., Haydon, N. From the experimentalist disposition to the absolute : Peirce's pragmatic naturalism // Responses to naturalism : critical perspectives from idealism and pragmatism. New York ; London : Routledge, Taylor & Francis Group, 2019. p. 167-183.
https://doi.org/10.4324/9781315180854 https://www.taylorfrancis.com/books/9781315180854/chapters/10.4324/9781315180854-8 - Nester, C.M. Concurrent process histories and resource transducers // Logical methods in computer science (2023) vol. 19, 1, p. 7:1-7:22 : ill.
https://doi.org/10.46298/LMCS-19(1:7)2023 - Roman Garcia, M. Promonads and string diagrams for effectful categories : preprint // arXiv.org (2022) arXiv:2205.07664
https://doi.org/10.48550/arXiv.2205.07664 - Boisseau, G., Nester, C.M., Roman Garcia, M. Cornering optics : preprint // arXiv.org (2022) arXiv:2205.00842
https://doi.org/10.48550/arXiv.2205.00842 - Di Liberti, I., Loregian, F. Accessibility and presentability in 2-categories // Journal of pure and applied algebra (2023) vol. 227, 1, art. 107155, 25 p.
https://doi.org/10.1016/j.jpaa.2022.107155 - Di Lavore, E., Sobocinski, P.M. Monoidal width // Logical methods in computer science (2023) vol. 19, 3, p. 15:1–15:46 : ill.
https://doi.org/10.46298/LMCS-19(3:15)2023 - Braithwaite, D., Roman Garcia, M. Collages of string diagrams // arXiv.org (2023) arXiv:2305.02675, p. 39-53 : ill.
https://doi.org/10.48550/arXiv.2305.02675 - Hefford, J., Roman Garcia, M. Optics for premonoidal categories // arXiv.org (2023) arXiv:2312.08138, p. 152-171 : ill.
https://doi.org/10.48550/arXiv.2305.02906 - Loregian, F., Trimble, T. Differential 2-rigs // arXiv.org. New York : Cornell University, 2022. 16 p. : ill.
https://doi.org/10.48550/arXiv.2103.00938 https://msp.cis.strath.ac.uk/act2022/papers/ACT2022_paper_4413.pdf - Di Lavore, E., Gianola, A., Roman Garcia, M., Sabadini, N., Sobocinski, P. Span(Graph) : a canonical feedback algebra of open transition systems // Software and systems modeling (2023) vol. 22, 2, p. 495-520 : ill.
https://doi.org/10.1007/s10270-023-01092-7 - Genovese, F., Loregian, F., Puca, C. Fibration linguistics (FibLang) : language acquisition // arXiv.org. New York : Cornell University, 2022. p. 1-16 : ill.
https://doi.org/10.48550/arXiv.2207.06765 https://arxiv.org/pdf/2207.06765.pdf - Di Lavore, E., Roman Garcia, M. Evidential decision theory via partial Markov categories // 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) : Boston, MA, USA : 26-29 June 2023. Piscataway, NJ : IEEE, 2023. 14 p. : ill.
https://doi.org/10.1109/LICS56636.2023.10175776 - Di Lavore, E., Sobocinski, P.M. Monoidal width : capturing rank width // Proceedings Fifth International Conference on Applied Category Theory : Glasgow, Scotland, 18-22 July 2022. : Open Publishing Association, 2023. p. 268-283 : ill. (Electronic Proceedings in Theoretical Computer Science (EPTCS) ; 380).
https://doi.org/10.4204/EPTCS.380.16