Differences

This shows you the differences between two versions of the page.

--- start [2025/11/17 14:50] – anna.frid
+++ start [2025/12/12 20:34] (current) – anna.frid
@@ Line 23: / Line 23: @@
+**January 6 2026: Louis Marin** //Maximal 2-dimensional binary words of bounded degree//
+(Authors: Alexandre Blondin Massé, Alain Goupil, Raphael L'Heureux, Louis Marin)
-**November 25 2025: [[https://bicyt.conicet.gov.ar/fichas/p/ignacio-agustin-mollo-cunningham|Ignacio Mollo]]** //Is fully shuffling a rational operation?//
+Let $d$ be an integer between $0$ and $4$, and $W$ be a $2$-dimensional word of dimensions $h \times w$ on the binary alphabet $\{0, 1\}$, where $h, w \in \mathbb Z > 0$. Assume that each occurrence of the letter $1$ in $W$ is adjacent to at most $d$ letters $1$. We provide an exact formula for the maximum number of letters $1$ that can occur in $W$ for fixed $(h, w)$. As a byproduct, we deduce an upper bound on the length of maximum snake polyominoes contained in a $h \times w$ rectangle.
-A shuffler is a 3-tape transducer specialized in the shuffling of words. These automata define rational sets in the so-called shuffling monoid, which map directly to regular shuffle languages. In this talk we look at rational relations of words and wonder whether their full shuffle is rational: we conclude that it's very rare that the full shuffle of a rational relation remains rational but find very interesting examples where rationality can be assured.
-** December 9 2025: Florin Manea**
-**December 23 2025: Savinien Kreczman**
+**January 20 2026: Savinien Kreczman**
-**January 6 2026: Louis Marin**
-**January 20 2026: Léo Vivion**
 **February 3 2026: Annika Huch **
@@ Line 45: / Line 41: @@
 **March 17 2026: Gwenael Richomme**
-**March 30 2026: Paulina Cecchi Bernales**
+**March 31 2026: Paulina Cecchi Bernales**
 **April 14 2026: Idrissa Kaboré** //On modulo-recurrence and window complexity in infinite words//
@@ Line 53: / Line 49: @@
 **April 28 2026: [[https://kmlinux.fjfi.cvut.cz/~balkolub/| Ľubomíra Dvořáková]]** //Attractors of sequences coding beta-integers//
+**May 12 2026: Léo Vivion**
+**May 26 2026: Reem Yassawi**
 ==== Past talks 2025 ====
+** December 9 2025: [[https://flmanea.blogspot.com/|Florin Manea]]** //Linear Time Subsequence and Supersequence Regex Matching//
+{{ seminar2025:20251209manea.pdf |slides by Tina Ringleb (Uni Göttingen)}}
+{{ seminar2025:20251209manea.mp4 |video of the talk}}
+It is well-known that checking whether a given string $w$ matches a given regular expression $r$ can be done in quadratic time $O(|w|⋅ |r|)$ and that this cannot be improved to a truly subquadratic running time of $O((|w|⋅ |r|)^{1-\varepsilon})$ assuming the strong exponential time hypothesis (SETH). We study a different matching paradigm where we ask instead whether $w$ has a subsequence that matches $r$, and show that regex matching in this sense can be solved in linear time $O(|w| + |r|)$. Further, the same holds if we ask for a supersequence. We show that the quantitative variants where we want to compute a longest or shortest subsequence or supersequence of w that matches $r$ can be solved in $O(|w|⋅ |r|)$, i. e., asymptotically no worse than classical regex matching; and we show that $O(|w| + |r|)$ is conditionally not possible for these problems. We also investigate these questions with respect to other natural string relations like the infix, prefix, left-extension or extension relation instead of the subsequence and supersequence relation. We further study the complexity of the universal problem where we ask if all subsequences (or supersequences, infixes, prefixes, left-extensions or extensions) of an input string satisfy a given regular expression.
+This is based on the paper: Antoine Amarilli, Florin Manea, Tina Ringleb, Markus L. Schmid: Linear Time Subsequence and Supersequence Regex Matching. MFCS 2025: 9:1-9:19
+**November 25 2025: [[https://bicyt.conicet.gov.ar/fichas/p/ignacio-agustin-mollo-cunningham|Ignacio Mollo]]** //Is fully shuffling a rational operation?//
+{{ seminar2025:20251125mollo.pdf |slides}}
+{{ seminar2025:20251125mollo.mp4 |video of the talk}}
+A shuffler is a 3-tape transducer specialized in the shuffling of words. These automata define rational sets in the so-called shuffling monoid, which map directly to regular shuffle languages. In this talk we look at rational relations of words and wonder whether their full shuffle is rational: we conclude that it's very rare that the full shuffle of a rational relation remains rational but find very interesting examples where rationality can be assured.
 **November 11 2025: [[https://www.utu.fi/en/people/aleksi-vanhatalo|Aleksi Vanhatalo]]** //Exponents of words under injective morphisms//