Matthew David Earnshaw, the PhD student of the Department of Software Science, will defend his PhD thesis "Languages of String Diagrams" on January, 15, 2025 starting at 14:00. The defense will take place in room ICT-638 (Akadeemia tee 15a, ICT building of TalTech) and can be also followed via Zoom.
In thesis "Languages of String Diagrams" we introduce and investigate the theory of regular and context-free languages of string diagrams, considered as morphisms in monoidal categories. The former class includes regular languages of words, trees, and Mazurkiewicz traces. We introduce a pumping lemma and investigate deterministic recognizability. The example of trace languages leads to a refinement of string diagrams for effectful categories, and a construction of their commuting tensor product. Context-free languages of string diagrams include classical context-free languages of words, trees and hypergraphs, when established over appropriate monoidal categories. We prove a representation theorem that links the two classes of languages, inspired by the Chomsky-Schützenberger representation theorem.
The thesis is published in the Digital Collection of TalTech Library.
Supervisor: Prof. Pawel Maria Sobocinski, TalTech, Estonia.
Oponents:
- Prof. Bartek Klin, University of Oxford, United Kingdom;
- Prof. Noam Zeilberger, Laboratoire d’informatique de l’École Polytechnique, France.
Meeting ID: 986 2976 0936
Passcode: 048623