Differences

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

--- start [2026/01/12 19:12] – anna.frid
+++ start [2026/02/10 14:43] (current) – anna.frid
@@ Line 22: / Line 22: @@
 ==== Upcoming talks ====
-**January 20 2026: Savinien Kreczman** //Factor complexity and critical exponent of words in a Thue-Morse family//
+**February 17 2026: [[https://sites.google.com/view/stevenrobertson|Steven Robertson]]** //Number walls of automatic sequences//
-The Thue-Morse, Fibonacci-Thue-Morse and Allouche-Johnson words are related to the binary, Zeckendorf and Narayana numeration systems respectively, as they count the parity of the number of ones in representations of natural numbers in those systems. These three numeration systems can be seen as the special cases for k=1,2,3 of a positional numeration system based on the recurrence relation $U_n=U_{n-1}+U_{n-k}$. As such, the three words above can be seen as the first elements in a family of binary words related to those numeration systems.
+Given any one-dimensional sequence S, one can generate a unique two-dimensional sequence by considering the determinants of the Toeplitz matrices defined by S. This is known as the number wall of S. It is conjectured that if S is automatic, then the number wall of S is itself a two-dimensional automatic sequence. In this talk, we will discuss evidence towards this conjecture as well as some recent partial results. The talk aims to be accessible for people with no experience of number walls.
-In a recent preprint, J.Shallit put forth two conjectures on words of this family, the first concerning the first difference of their factor complexity and the second concerning their asymptotic critical exponent. In this talk, we will prove both conjectures by studying bispecial factors within those words. We will highlight a method by K.Klouda allowing us to fully list those bispecial factors and show how this list allows us to attack the conjectures in question.
-Joint work with L'ubomíra Dvořáková and Edita Pelantová.
-**February 3 2026: Annika Huch **
-**February 17 2026: Steven Robertson**
 **March 03 2026: Ingrid Vukusic**
@@ Line 48: / Line 42: @@
 **May 26 2026: Reem Yassawi**
+**July 7 2026: Delaram Moradi**
 ==== Past talks 2026 ====
-**January 6 2026: Louis Marin** //Maximal 2-dimensional binary words of bounded degree//
-(Authors: Alexandre Blondin Massé, Alain Goupil, Raphael L'Heureux, Louis Marin)
+**February 3 2026: [[https://scholar.google.com/citations?user=65FAE84AAAAJ&hl=de|Annika Huch]] ** //A Word Reconstruction Problem for Polynomial Regular Languages//
-{{ seminar2026:20260106marin.pdf |slides}}
+{{ seminar2026:20260203huch.pdf |slides}}
-{{ seminar2026:20260106marin.mp4 |video of the talk}}
+{{ seminar2026:20260203huch.mp4 |video of the talk}}
+The reconstruction problem concerns the ability to uniquely determine an unknown word from querying information on the number of occurrences of chosen subwords. In the joined work with M. Golafshan and M. Rigo we focused on the reconstruction problem when the unknown word belongs to a known polynomial regular language, i.e.,
+its growth function is bounded by a polynomial. Exploiting the combinatorial and structural properties of these languages, we are able to translate queries into polynomial equations and transfer the problem of unique reconstruction to finding those sets of queries such that their polynomial equations have a unique integer solution.
-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.
+**January 20 2026: [[https://orbi.uliege.be/profile?uid=p207127|Savinien Kreczman]]** //Factor complexity and critical exponent of words in a Thue-Morse family//
-==== Past talks 2025 ====
+{{ seminar2026:20260120kreczman.pdf |slides}}
-** December 9 2025: [[https://flmanea.blogspot.com/|Florin Manea]]** //Linear Time Subsequence and Supersequence Regex Matching//
+{{ seminar2026:20260120kreczman.mp4 |video of the talk}}
-{{ seminar2025:20251209manea.pdf |slides by Tina Ringleb (Uni Göttingen)}}
+The Thue-Morse, Fibonacci-Thue-Morse and Allouche-Johnson words are related to the binary, Zeckendorf and Narayana numeration systems respectively, as they count the parity of the number of ones in representations of natural numbers in those systems. These three numeration systems can be seen as the special cases for k=1,2,3 of a positional numeration system based on the recurrence relation $U_n=U_{n-1}+U_{n-k}$. As such, the three words above can be seen as the first elements in a family of binary words related to those numeration systems.
-{{ seminar2025:20251209manea.mp4 |video of the talk}}
+In a recent preprint, J.Shallit put forth two conjectures on words of this family, the first concerning the first difference of their factor complexity and the second concerning their asymptotic critical exponent. In this talk, we will prove both conjectures by studying bispecial factors within those words. We will highlight a method by K.Klouda allowing us to fully list those bispecial factors and show how this list allows us to attack the conjectures in question.
+Joint work with L'ubomíra Dvořáková and Edita Pelantová.
+**January 6 2026: Louis Marin** //Maximal 2-dimensional binary words of bounded degree//
-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.
+(Authors: Alexandre Blondin Massé, Alain Goupil, Raphael L'Heureux, Louis Marin)
-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
+{{ seminar2026:20260106marin.pdf |slides}}
+{{ seminar2026:20260106marin.mp4 |video of the talk}}
-**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//
-{{ seminar2025:20251014julien.pdf |slides}}
-{{ seminar2025:20251014julien.mp4 |video of the talk}}
-This presentation is concerned with hypercubic billiards with irrational trajectories. In this talk, I will present the relationship between balance properties in hypercubic billiards, and subshift cohomology.
-More precisely, I will define cohomology for subshifts and (time permitting) illustrate with examples of how cohomology has previously been used in symbolic dynamics. Then, I will present the link between cohomology and balance for billiard sequences. Finally, I will explain how results of Kellendonk and Sadun on the dimension of some cohomology spaces implies that billiard words in cubes of dimension at least 3 cannot be balanced on all factors.
-In the case of billiards in the cube, we also showed (using other methods) that these sequences are not balanced on factors of length 2.
-Joint work with Nicolas Bédaride and Valérie Berthé.
-**September 16 2025: Kaisei Kishi** //Net Occurrences in Fibonacci and Thue-Morse Words//
-{{ seminar2025:20250916kishi.pdf |slides}}
-{{ seminar2025:20250916kishi.mp4 |video of the talk}}
-In a string $T$, an occurrence of a substring $S=T[i ... j]$ is a net occurrence if $S$ is repeated in $T$, while both left extension $T[i-1, ... j]$ and right extension $T[i, ... j+1]$ are unique in $T$. The number of net occurrences of $S$ in $T$ is called its net frequency. Compared with ordinary frequency, net frequency highlights the more significant occurrences of $S$ in $T$. In this talk, I will present several properties of net occurrences and describe techniques to identify all the net occurrences in Fibonacci and Thue-Morse words. In particular, I will explain the technique to characterize the occurrences of smaller-order Fibonacci and Thue-Morse words. This is a joint work with Peaker Guo.
-**September 2 2025: Gandhar Joshi** //Monochromatic Arithmetic Progressions in Sturmian sequences//
-{{ seminar2025:20250902joshi.pdf |slides}}
-{{ seminar2025:20250902joshi.mp4 |video of the talk}}
-This is joint work with Dan Rust. We define Monochromatic arithmetic progression (MAP) as the repetition of a symbol (traditionally colour) with a constant difference in a sequence. We study thresholds of the lengths of MAPs in the Fibonacci word in our paper https://doi.org/10.1016/j.tcs.2025.115391, which not only resolves a few problems left open by previous works revolving around MAPs in symbolic sequences but also reveals a straightforward method to find a formula that finds longest lengths of MAPs for all Sturmians. This extension is dealt with in the author's PhD thesis.
-**July 15 2025: [[https://apacz.matinf.uj.edu.pl/users/1719-elzbieta-krawczyk|Elżbieta Krawczyk]]**  //Quasi-fixed points of substitutions and substitutive systems//
-{{ seminar2025:20250715krawczyk.pdf |slides}}
-{{ seminar2025:20250715krawczyk.mp4 |video of the talk}}
-We study automatic sequences and automatic systems (symbolic dynamical systems) generated by general constant length (nonprimitive) substitutions. While an automatic system is typically uncountable, the set of automatic sequences is countable, implying that most sequences within an automatic system are not themselves automatic. We provide a complete classification of automatic sequences that lie in a given automatic system in terms of the so-called quasi-fixed points of the substitution defining the system. Quasi-fixed points have already appeared implicitly in a few places (e.g. in the  study of substitutivity of lexicographically minimal points in substitutive systems or in the study of subsystems of substitutive systems) and they have been described in detail by Shallit and Wang and, more recently, Béal, Perrin, and Restivo . We conjecture that a similar statement holds for general nonconstant length substitutions.
-**June 17 2025: [[https://sites.google.com/view/noysofferaranov/bio|Noy Soffer Aranov]]** //Escape of Mass of Sequences//
-{{ seminar2025:20250617aranov.pdf |slides}}
-{{ seminar2025:20250617aranov.mp4 |video of the talk}}
-One way to study the distribution of nested quadratic number fields satisfying fixed arithmetic relationships is through the evolution of continued fraction expansions. In the function field setting, it was shown by de Mathan and Teullie that given a quadratic irrational $\Theta$, the degrees of the periodic part of the continued fraction of $t^n\Theta$ are unbounded. Paulin and Shapira improved this by proving that quadratic irrationals exhibit partial escape of mass. Moreover, they conjectured that they must exhibit full escape of mass. We construct counterexamples to their conjecture in every characteristic. In this talk we shall discuss the technique of proof as well as the connection between escape of mass in continued fractions, Hecke trees, and number walls. This is part of joint works with Erez Nesharim and Uri Shapira and with Steven Robertson.
-**June 3 2025: [[https://www.curtisbright.com/|Curtis Bright]]** //Mathematical Problems with SATisfying Solutions//
-Automated reasoning tools have been effectively used to solve a variety of problems in discrete mathematics.  In this talk, I will introduce satisfiability (SAT) solvers and highlight a variety of problems in discrete mathematics that have been tackled with a SAT solver.  As a case study, I will demonstrate how a SAT solver can be used to make progress on a question arising in combinatorics on words involving North-East lattice paths.
-{{ seminar2025:20250603bright.pdf |slides}}
-{{ seminar2025:20250603bright.mp4 |video of the talk}}
-**May 20 2025: [[https://www.researchgate.net/profile/Pranjal-Jain-10|Pranjal Jain]]** //Partial Sums of Binary Subword-Counting Sequences//
-{{ seminar2025:20250520jain.pdf |slides}}
-{{ seminar2025:20250520jain.mp4 |video of the talk}}
-Let $w$ be a finite word over the alphabet $\{0,1\}$. For any natural number $n$, let $s_w(n)$ denote the number of occurrences of $w$ in the binary expansion of $n$ as a scattered subsequence. The talk aims to provide a systematic way of studying the growth of the partial sum $\sum_{n=0}^N (-1)^{s_w(n)}$ as $N \to \infty$. In particular, these techniques yield several classes of words $w$ with $\sum_{n=0}^N (-1)^{s_w(n)} = O(N^{1-\epsilon})$ for some $\epsilon >0$. We begin by motivating the ideas using the case of $w=01,011$. The talk is based on joint work with Shuo Li.
-**May 6 2025: Jarkko Peltomäki** //The repetition threshold for ternary rich words//
-{{ seminar2025:20250506peltomaki.pdf |slides}}
-{{ seminar2025:20250506peltomaki.mp4 |video of the talk}}
-In the recent years, it has been popular to determine the least critical exponent in specific families of infinite words. In this talk, I will explain what is known about the least critical exponents for infinite words that are rich in palindromes. In particular, I will outline the proof of our result that the least critical exponent for ternary rich infinite words equals $1 + 1/(3 - \mu) \approx 2.25876324$, where $\mu$ is the unique real root of the polynomial $x^3 - 2x^2 - 1$. This result is based on proving a structure theorem for ternary rich infinite words that avoid $16/7$-powers. In addition, I discuss some recent progress on determining the least asymptotic critical exponents for rich infinite words.
-Joint work with L. Mol and J. D. Currie.
-**April 22 2025: [[https://sites.google.com/view/beeri-greenfeld|Be'eri Greenfeld]]** //On the Complexity of Infinite Words//
-{{ seminar2025:20250422greenfeld.mp4 |video of the talk}}
-Given an infinite word $w$, its complexity function $p_w(n)$ counts the number of distinct subwords of length $n$ it contains. A longstanding open problem in the combinatorics of infinite words is the {\it inverse problem}: describe which functions $f: \mathbb N \to \mathbb N$ arise as complexity functions of infinite words. Such functions must be non-decreasing and, unless eventually constant, strictly increasing; they must also be submultiplicative, i.e., $f(n+m)≤f(n)f(m)$. Many interesting results, both positive and negative, have been obtained in this direction.
-We resolve this problem up to asymptotic equivalence in the sense of large-scale geometry. Specifically, given any increasing, submultiplicative function $f$, we construct an infinite recurrent word $w$ such that $c f(cn) ≤ p_w(n) ≤ d f(dn)$ for some constants $c,d>0$. For uniformly recurrent words, we obtain a weaker version allowing a linear error factor. Time permitting, we will discuss connections and applications of these results to asymptotic questions in algebra.
-Joint work with C. G. Moreira and E. Zelmanov.
-**April 8 2025: [[https://trios.tsukuba.ac.jp/en/researcher/0000003624|Hajime Kaneko]]** //Analogs of Markoff and Lagrange spectra on
-one-sided shift spaces//
-{{ seminar2025:20250408kaneko.pdf |slides}}
-{{ seminar2025:20250408kaneko.mp4 |video of the talk}}
-The Lagrange spectrum is related to the rational approximations of badly
-approximable numbers. The discrete part of the spectrum is denoted in terms
-of Christoffel words. A multiplicative analog of the Lagrange spectrum was
-recently investigated, which is defined by Diophantine approximations of geometric sequences and more general linear recurrences. Dubickas investigated
-the minimal limit points of certain multiplicative Markoff-Lagrange spectra in
-terms of symbolic dynamical systems and certain substitutions.
-In this talk, we study an analog of the Markoff-Lagrange spectrum for general
-one-sided shift spaces. As our main results, we determine the discrete parts and
-minimal limit points in terms of $S$-adic sequences, where $S$ is an infinite set of
-substitutions. This is joint work with Wolfgang Steiner.
-**March 25 2025: [[https://page.mi.fu-berlin.de/vbui/|Vuong Bui]]** //An explicit condition for boundedly supermultiplicative subshifts//
-{{ seminar2025:20250325bui.pdf |slides}}
-{{ seminar2025:20250325bui.mp4 |video of the talk}}
-We study some properties of the growth rate of  $L(A,F)$, that is, the language of words over the alphabet $A$ avoiding the set of forbidden factors $F$. We first provide a sufficient condition on $F$ and $A$ for the growth of $L(A,F)$ to be boundedly supermultiplicative.  That is, there exist constants $C>0$ and $\alpha\ge 0$, such that for all $n$, the number of words of length $n$ in $L(A,F)$ is between $\alpha^n$ and $C\alpha^n$. In some settings, our condition provides a way to compute $C$, which implies that $\alpha$, the growth rate of the language, is also computable whenever our condition holds.
-We also apply our technique to the specific setting of power-free words where the argument can be slightly refined to provide better bounds. Finally, we apply a similar idea to $F$-free circular words and in particular we make progress toward a conjecture of Shur about the number of square-free circular words.
-**March 11 2025:[[https://www.irif.fr/users/letouzey/index|Pierre Letouzey]]** //Generalizing some Hofstadter functions: G, H and beyond//
-{{ seminar2025:20250311letouzey.pdf |slides}}
-Hofstadter's G function is recursively defined via $G(0)=0$ and then
-$G(n)=n-G(G(n-1))$. Following Hofstadter, a family $(F_k)$ of similar
-functions is obtained by varying the number $k$ of nested recursive calls
-in this equation. We present here a few nice properties of these functions.
-In particular, they can be described via some infinite morphic words
-generalizing the Fibonacci word. This was crucial for proving that
-this family is ordered pointwise: for all $k$ and $n$, $F_k(n) \le F_{k+1}(n)$.
-Moreover, these functions have a simple behavior on well-chosen numerical
-representations (Zeckendorf decompositions for some Fibonacci-like sequences).
-Thanks to that, we were also able to estimate the discrepancies for these $F_k$,
-i.e. the maximal distances between each $F_k$ and its linear equivalent.
-This whole work was formally proved using the Coq proof assistant
-(except for a beautiful fractal !) and we will give a gentle introduction
-to this Coq development.
-Joint work with Shuo Li (U. Winnipeg) and Wolfgang Steiner (IRIF, Paris).
-**February 25 2025: [[https://ms.polsl.pl/pracownik.php?kod=pawl|Bartek Pawlik]]** //Words Avoiding Tangrams//
-{{ seminar2025:20250225pawlik.pdf |slides}}
-{{ seminar2025:20250225pawlik.mp4 |video of the talk}}
-Work in collaboration with Michał Dębski, Jarosław Grytczuk, Jakub Przybyło and Małgorzata Śleszyńska-Nowak.
-If, in a given word $W$, each letter appears an even number of times, then $W$ can be split into two identical, disjoint subwords. For example, the word $\mathtt{hotshots}$ can be split into two $\mathtt{hots}$ by dividing the word exactly in the middle: $\mathtt{hots\,|\,hots}$. More generally, any square can be separated into two identical words with a single cut. The word $\mathtt{tattletale}$ requires three cuts: $\mathtt{tat\,|\,tle\,|\,ta\,|\,le}$ to split it into two words $\mathtt{tatle}$. The minimal number of cuts needed to divide a word $W$ into two identical subwords is called the //cut number// of $W$. During the lecture, I will discuss several topics related to the cut number.
-**February 11 2025: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Palindromic length of infinite aperiodic words//
-{{ seminar2025:20250211rukavicka.pdf |slides}}
-{{ seminar2025:20250211rukavicka.mp4 |video of the talk}}
-The palindromic length of the finite word $v$ is equal to the minimal number of palindromes whose concatenation is equal to $v$. It was conjectured in 2013 that for every infinite aperiodic word $x$, the palindromic length of its factors is not bounded.
-We prove this conjecture to be true.
-Here is [[https://arxiv.org/abs/2410.12714|the paper]].
-**January 28 2025: [[https://faculty.tru.ca/lmol/|Lucas Mol]]** //Avoiding abelian and additive powers in rich words//
-{{ seminar2025:20250128mol.pdf |slides}}
-{{ seminar2025:20250128mol.mp4 |video of the talk}}
-We construct an infinite additive 5-power-free rich word over $\{0,1\}$ and an infinite additive 4-power-free rich word over $\{0,1,2\}$.  Both constructions involve affine morphisms, for which the length and sum of the images of the letters are linear functions of the letters.  This allows us to prove the additive power-freeness of our constructions using a recent variation of the template method due to Currie, Mol, Rampersad, and Shallit.
-**January 14 2025: [[https://reutenauer.math.uqam.ca|Christophe Reutenauer]]** //Christoffel matrices and Sturmian determinants//
+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.
-{{ seminar2025:20250114reutenauer.mp4 |video of the talk}}
-Work in collaboration with Jeffrey Shallit.
-. The set of Christoffel matrices (that is, Burrows-Wheeler matrices of Christoffel words) of size $n$ by $n$, where the alphabet is some commutative ring $R$, form a monoid under multiplication, and those which are invertible, form a subgroup of $GL_n(R)$.
-(this result was also obtained independently by Luca Zamboni)
-. The determinant of a Christoffel matrix has a simple form, using the Zolotareff symbol (the latter extends the Jacobi symbol).
-. Taking $n$ factors of length $n$ of a Sturmian sequence over $0$,  $1$, one obtains a matrix and a determinant. There are$n+1$ such determinants; ordering them suitably, these $n+1$ determinants form a word on a two- or three-letter alphabet contained in $Z$; this word is perfectly clustering. If there are three letters, then one of them is the sum of the two others.
+==== Archives 2025 ====
+The talks of 2025 are available [[2025|here]].