Differences

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

--- start [2025/10/28 09:50] – anna.frid
+++ start [2025/12/12 20:34] (current) – anna.frid
@@ Line 23: / Line 23: @@
-**October 28 2025: Idrissa Kaboré** //On modulo-recurrence and window complexity in infinite words//
+**January 6 2026: Louis Marin** //Maximal 2-dimensional binary words of bounded degree//
-In this talk, first, I will recall the notions of modulo-recurrent words and of window complexity. These notions are introduced in 2007. Then, I present some properties of these notions. After that, I will present the notions of uniform modulo-recurrence and of strong modulo-recurrence. These notions are defined recently in a joint work with Julien Cassaigne. Sturmian words are uniformly (resp. strongly) modulo-recurrent words. Then, I will address the window complexity of the Thue-Morse. To finish, I will present a recurrent aperiodic word with bounded window complexity.
+(Authors: Alexandre Blondin Massé, Alain Goupil, Raphael L'Heureux, Louis Marin)
-**November 11 2025: Aleksi Vanhatalo** //Exponents of words under injective morphisms//
+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 very common problem type in combinatorics on words is to construct words (under constraints) that avoid repetition. This is often done by constructing suitable morphisms.
-Here we flip the setup: we ask how good morphisms are at introducing repetitions into words. Periodic morphisms are trivially very good at this, but how about less trivial classes of morphisms?
-We consider a few variations of this question. We characterize finite words that do not have an upper bound on fractional or integer exponents when mapped via injective morphisms. Then we consider the asymptotic critical exponent of infinite words. While we consider all finite alphabet sizes, these variations are better understood in the binary case.
-This talk is an extended version of the one presented at DLT 2025. It is based on joint work with Eva Foster and Aleksi Saarela, and on ongoing research.
+**January 20 2026: Savinien Kreczman**
+**February 3 2026: Annika Huch **
-**November 25 2025: Ignacio Mollo**
+**February 17 2026: Steven Robertson**
-** December 9 2025: Florin Manea**
+**March 03 2026: Ingrid Vukusic**
-**December 23 2025: Savinien Kreczman**
+**March 17 2026: Gwenael Richomme**
-**January 6 2026: Louis Marin**
+**March 31 2026: Paulina Cecchi Bernales**
-**January 20 2026: Léo Vivion**
+**April 14 2026: Idrissa Kaboré** //On modulo-recurrence and window complexity in infinite words//
-**February 3 2026: Annika Huch **
+In this talk, first, I will recall the notions of modulo-recurrent words and of window complexity. These notions are introduced in 2007. Then, I present some properties of these notions. After that, I will present the notions of uniform modulo-recurrence and of strong modulo-recurrence. These notions are defined recently in a joint work with Julien Cassaigne. Sturmian words are uniformly (resp. strongly) modulo-recurrent words. Then, I will address the window complexity of the Thue-Morse. To finish, I will present a recurrent aperiodic word with bounded window complexity.
-**February 17 2026: Steven Robertson**
+**April 28 2026: [[https://kmlinux.fjfi.cvut.cz/~balkolub/| Ľubomíra Dvořáková]]** //Attractors of sequences coding beta-integers//
-**March 03 2026: Ingrid Vukusic**
+**May 12 2026: Léo Vivion**
-**March 17 2026: Gwenael Richomme**
+**May 26 2026: Reem Yassawi**
-**March 30 2026: Paulina Cecchi Bernales**
 ==== 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//
+{{ seminar2025:20251111vanhatalo.pdf |slides}}
+{{ seminar2025:20251111vanhatalo.mp4 |video of the talk}}
+A very common problem type in combinatorics on words is to construct words (under constraints) that avoid repetition. This is often done by constructing suitable morphisms.
+Here we flip the setup: we ask how good morphisms are at introducing repetitions into words. Periodic morphisms are trivially very good at this, but how about less trivial classes of morphisms?
+We consider a few variations of this question. We characterize finite words that do not have an upper bound on fractional or integer exponents when mapped via injective morphisms. Then we consider the asymptotic critical exponent of infinite words. While we consider all finite alphabet sizes, these variations are better understood in the binary case.
+This talk is an extended version of the one presented at DLT 2025. It is based on joint work with Eva Foster and Aleksi Saarela, and on ongoing research.
 **October 14 2025: [[https://www.nord.no/en/about/employees/antoine-laurent-christophe-julien|Antoine Julien]]** //On balance properties of hypercubic billiard words//