Differences

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

--- start [2025/11/26 16:40] – anna.frid
+++ start [2025/12/12 20:34] (current) – anna.frid
@@ Line 22: / Line 22: @@
 ==== Upcoming talks ====
-** December 9 2025: [[https://flmanea.blogspot.com/|Florin Manea]]** //Linear Time Subsequence and Supersequence Regex Matching//
-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.
+**January 6 2026: Louis Marin** //Maximal 2-dimensional binary words of bounded degree//
-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
+(Authors: Alexandre Blondin Massé, Alain Goupil, Raphael L'Heureux, Louis Marin)
+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.
-**December 23 2025: Savinien Kreczman**
-**January 6 2026: Louis Marin**
-**January 20 2026: Léo Vivion**
+**January 20 2026: Savinien Kreczman**
 **February 3 2026: Annika Huch **
@@ Line 43: / 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 50: / Line 48: @@
 **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**
@@ Line 55: / Line 55: @@
 ==== 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