skip to content

Department of Computer Science and Technology

Invited speakers

Mikołaj Bojańczyk - Recognisable languages over monads

Abstract: Algebraic language theory is the study of regular languages via algebras, such as semigroups or monoids, as opposed to automata. This approach dates back to work of Schützenberger in the 1950s, and is hence roughly as old as automata theory. In time, algebraic language theory has broadened to cover objects beyond words, e.g. trees or graphs. In my talk I will discuss how monads – and their Eilenberg-Moore algebras – can be seen as a unifying framework for such algebras. Such a unifying framework seems particularly important in some frontiers of algebraic language theory, e.g. in the study of graphs or infinite trees, where it is still not exactly clear what the right algebraic approach is supposed to be.

Referrences:

  1. Mikołaj Bojańczyk. “Languages recognised by finite semigroups and their generalisations to objects such as trees and graphs with an emphasis on definability in Monadic Second-Order logic”, lecture notes, 2020.

 

Laura Mančinska - Quantum Isomorphism of Graphs: an Overview

Abstract: In this talk I will introduce a quantum version of graph isomorphism. Our point of departure will be an interactive protocol (nonlocal game) where two provers try to convince a verifier that two graphs are isomorphic. Allowing provers to take advantage of shared quantum resources will then allow us to define quantum isomorphism as the ability of quantum players to win the corresponding game with certainty. We will see that quantum isomorphism can be naturally reformulated in the languages of quantum groups and counting complexity. In particular, we will see that two graphs are quantum isomorphic if and only if they have the same homomorphism counts from all planar graphs.

References:

  1. Laura Mančinska, David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. arXiv:1910.06958

  2. Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms. arXiv:1611.09837

 

Daniela Petrişan - Learning Automata and Transducers: A Categorical Approach

Abstract: We present a categorical approach to learning automata over words, in the sense of the L*-algorithm of Angluin. This yields a new generic L*-like algorithm which can be instantiated for learning deterministic automata, automata weighted over fields, as well as subsequential transducers. The generic nature of our algorithm is obtained by adopting an approach in which automata are simply functors from a particular category representing words to a "computation category". We establish that the sufficient properties for yielding the existence of minimal automata, in combination with some additional hypotheses relative to termination, ensure the correctness of our generic algorithm.

This is joint work with Thomas Colcombet and Riccardo Stabile, and was published in CSL'21: https://drops.dagstuhl.de/opus/volltexte/2021/13449/

[RECORDING]

 

Accepted contributions

  • Heba Aamer – Input–Output Disjointness for Forward Expressions in the Logic of Information Flows [SLIDES,RECORDING]
  • Siddharth Bhaskar – Graph Traversals as Universal Constructions [SLIDES,RECORDING]
  • Achim Blumensath – Compositionality and Logical Definability for Monads [SLIDES,RECORDING]
  • Alexandre Goy – An Overview of Weak Distributive Laws [SLIDES,RECORDING]
  • Peter Hines – On the combinatorics of Girard's exponential [SLIDES,RECORDING]
  • Jan Hubička – Big Ramsey degrees using Ramsey theorem for trees with interesting levels [RECORDING]
  • Martti Karvonen – Categorical composable cryptography [SLIDES,RECORDING]
  • Steven Lindell – Traversal-invariant definability and Logarithmic-space computation [SLIDES,RECORDING]
  • Thor Nielsen – Glued magic games self-test maximally entangled states [SLIDES,RECORDING]
  • Jakub Opršal – A categorical approach to constraint satisfaction problem [SLIDES,RECORDING]
  • John Power – Flexibility for a 2-monad [SLIDES,RECORDING]
  • Pierre Pradic – Implicit automata in typed λ-calculi [SLIDES,RECORDING]
  • Nihil Shah – Bisimulation between hom sets and logics without counting [SLIDES,RECORDING]
  • Alexandros Singh – Asymptotic Distribution of Parameters in Trivalent Maps and Linear Lambda Terms [SLIDES,RECORDING]
  • Glynn Winskel – On games on algebras [SLIDES,RECORDING]
  • Noam Zeilberger – Complexity of untyped normalization for subsystems of linear lambda calculus [SLIDES,RECORDING]

The abstracts of contributed talks can be found here.