After the outbreak of the coronavirus pandemic, a few scientific communities faced cancellations of conferences, seminars, and research visits. Motivated by the need to establish new communication channels, a series of seminars called One World Seminars was initiated, as an attempt to keep the communities together. The pioneer of this project was One World Probability Seminar that inspired several other One World projects (among which, you might know the One World Combinatorics on Words Seminar).

This is a new series of online research seminars on topics related to Formal Languages and Automata Theory: One FLAT World Seminar (yes, we know, we broke a pattern here: we should have named it “One World FLAT Seminars”, but this name is funnier).

The main goal of this project is to keep the community working in our area alive and updated, by bringing together researchers from all over the world in a virtual, accessible, and inclusive environment. We believe that recently our community is quite fragmented, so having a common platform to share old and recent results on the one hand would help established researchers working on similar topics to find collaborators and fresh ideas and, on the other hand, young people, new in the area, would have a clear vision of what is going on in this branch of theoretical computer science.

The talks will be accessible via Zoom and will run, at least at the beginning, on a monthly basis.

Next talks

• Two-dimensional automata theory

  Decidability, complexity, and algorithms

  Speaker: Taylor Smith

  April 9, 2025 at 13:00 UTC (your local time: )

  

  

  A two-dimensional (2D) automaton is a natural extension of the finite automaton model that operates on two-dimensional words; that is, on arrays or matrices of symbols. The 2D automaton model has a long history dating back to the 1960s and many of the major results were established in the 1970s and 1980s, but there has been a resurgence of interest in variants of the model in the past decade or so. Since the standard 2D automaton model is Turing-equivalent and thus more difficult to reason about, recent work has focused on the properties of restricted variants of 2D automata: namely,... [Read More]

• On the intersection problem for quantum finite automata

  Speaker: Flavio D'Alessandro

  April 30, 2025 at 13:00 UTC (your local time: )

  

  

  In this talk we consider the quantum finite automata according to the model “measure-once” introduced by Moore and Crutchfield in the late 90’s. More precisely, we are interested in some results that prove the decidability of the Emptiness problem (for languages accepted by the model with strict threshold) obtained by Blondel, Jeandel, Koiran, and Portier, and of one of its generalisation, called the Intersection Problem, obtained by Bertoni, Choffrut et al. In this presentation, we will highlight, in particular, the role of algebraic groups in defining the aforementioned decidability constructs, and, time permitting, describe some recent developments.