One FLAT World Seminar


A Formal Languages and Automata Theory Seminar

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

  • On the difference set of two transducers and PRAX algorithms

    Speaker: Stavros Konstantinidis
    Post thumbnail
    Post thumbnail
    The first part of the talk deals with sets (languages) of all inputs \(w\in\Sigma^*\) on which the output sets of two given transducers \(S\) and \(T\) differ; formally \(\Delta(S,T) = \{ w\in\Sigma^* : S(w) \neq T(w)\}\), where \(S\) and \(T\) are finite transducers (nondeterministic, in general) with the same domain \(\Sigma\). How hard is the problem \(\{(S,T,w) : S(w) ≠ T(w)\}\) in general — that is the problem of deciding whether \(S(w) ≠ T(w)\) given \(S\), \(T\), and \(w\) — and when (at least) one of \(S,T\) is of a restricted type (e.g., finite-valued)? [Read More]