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

  • Synchronised shuffles and team automata

    Speaker: Nelma Moreira
    Post thumbnail
    Post thumbnail
    The shuffle operation has been extensively studied in formal language theory. Regular expressions with shuffle provide succinct representations for modelling concurrent systems. However, even for regular languages, shuffle is hard: membership is NP-complete, inequivalence is EXP-complete, the conversion to NFAs is in the worst-case exponential, and the conversion to DFAs is double exponential. There are also numerous open problems, such as establishing tight bounds for state complexity even for the shuffle of two words. Standard shuffle models the pure interleaving of two concurrent systems. To model synchronisation, and inspired in the Team Automata framework, synchronised shuffle operators allow us to... [Read More]
  • TBA

    Speaker: Stavros Konstantinidis
    Post thumbnail
    Post thumbnail