Differences

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

--- start [2025/11/07 11:17] – anna.frid
+++ start [2025/12/12 20:34] (current) – anna.frid
@@ Line 22: / Line 22: @@
 ==== Upcoming talks ====
-**November 11 2025: [[https://www.utu.fi/en/people/aleksi-vanhatalo|Aleksi Vanhatalo]]** //Exponents of words under injective morphisms//
-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.
+**January 6 2026: Louis Marin** //Maximal 2-dimensional binary words of bounded degree//
-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.
+(Authors: Alexandre Blondin Massé, Alain Goupil, Raphael L'Heureux, Louis Marin)
-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.
+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.
-**November 25 2025: Ignacio Mollo**
-** December 9 2025: Florin Manea**
+**January 20 2026: Savinien Kreczman**
-**December 23 2025: Savinien Kreczman**
-**January 6 2026: Louis Marin**
-**January 20 2026: Léo Vivion**
 **February 3 2026: Annika Huch **
@@ Line 50: / 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 58: / 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//
+{{ 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//