Differences

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

--- start [2025/01/28 18:36] – 139.124.146.3
+++ start [2025/12/12 20:34] (current) – anna.frid
@@ Line 14: / Line 14: @@
 [[http://www.i2m.univ-amu.fr/perso/anna.frid/|Anna E. Frid]], Aix-Marseille Université,
 [[http://ion.uwinnipeg.ca/~nrampers/|Narad Rampersad]], University of Winnipeg,
-[[https://cs.uwaterloo.ca/~shallit/|Jeffrey O. Sh\allit]], University of Waterloo,
+[[https://cs.uwaterloo.ca/~shallit/|Jeffrey O. Shallit]], University of Waterloo,
 [[https://www.manon-stipulanti.be/|Manon Stipulanti]], Université de Liège.
@@ Line 23: / Line 23: @@
-**February 11 2025: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Palindromic length of infinite aperiodic words//
+**January 6 2026: Louis Marin** //Maximal 2-dimensional binary words of bounded degree//
-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.
+(Authors: Alexandre Blondin Massé, Alain Goupil, Raphael L'Heureux, Louis Marin)
-We prove this conjecture to be true.
-Here is [[https://arxiv.org/abs/2410.12714|the paper]].
+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.
-**February 25 2025: Bartek Pawlik**
-**March 11 2025:[[https://www.irif.fr/users/letouzey/index|Pierre Letouzey]]** //Generalizing some Hofstadter functions: G, H and beyond//
-Hofstadter's G function is recursively defined via $G(0)=0$ and then
+**January 20 2026: Savinien Kreczman**
-$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 3 2026: Annika Huch **
+**February 17 2026: Steven Robertson**
+**March 03 2026: Ingrid Vukusic**
-**March 25 2025: Vuong Bui**
+**March 17 2026: Gwenael Richomme**
-**April 8 2025: Hajime Kaneko**
+**March 31 2026: Paulina Cecchi Bernales**
-**April 22 2025: Be'eri Greenfeld**
+**April 14 2026: Idrissa Kaboré** //On modulo-recurrence and window complexity in infinite words//
-**May 6 2025: Jarkko Peltomäki**
+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.
-**May 20 2025: Pranjal Jain**
+**April 28 2026: [[https://kmlinux.fjfi.cvut.cz/~balkolub/| Ľubomíra Dvořáková]]** //Attractors of sequences coding beta-integers//
-**June 3 2025: Curtis Bright**
-**June 17 2025: [[https://sites.google.com/view/noysofferaranov/bio|Noy Soffer Aranov]]**
-**July 15 2025: [[https://apacz.matinf.uj.edu.pl/users/1719-elzbieta-krawczyk|Elżbieta Krawczyk]]**  //Quasi-fixed points of substitutions and substitutive systems//
-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\'eal, Perrin, and Restivo . We conjecture that a similar statement holds for general nonconstant length substitutions.
+**May 12 2026: Léo Vivion**
+**May 26 2026: Reem Yassawi**
 ==== Past talks 2025 ====
-{{ seminar2024:20250128mol.pdf |slides}}
+** December 9 2025: [[https://flmanea.blogspot.com/|Florin Manea]]** //Linear Time Subsequence and Supersequence Regex Matching//
-{{ seminar2024:20250128mol.mp4 |video of the talk}}
+{{ seminar2025:20251209manea.pdf |slides by Tina Ringleb (Uni Göttingen)}}
+{{ seminar2025:20251209manea.mp4 |video of the talk}}
-**January 28 2025: [[https://faculty.tru.ca/lmol/|Lucas Mol]]** //Avoiding abelian and additive powers in rich words//
+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.
-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.
+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?//
-**January 14 2025: [[https://reutenauer.math.uqam.ca|Christophe Reutenauer]]** //Christoffel matrices and Sturmian determinants//
+{{ seminar2025:20251125mollo.pdf |slides}}
+{{ seminar2025:20251125mollo.mp4 |video of the talk}}
-{{ 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)$.
+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.
-(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.
+**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}}
-==== Past talks 2024 ====
-**December 17 2024: [[https://hyoka.ofc.kyushu-u.ac.jp/html/100021295_en.html|Yuto Nakashima]]** //On the Number of Non-equivalent Parameterized Squares in a String//
-{{ seminar2024:20241217nakashima.pdf |slides}}
+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?
-{{ seminar2024:20241217nakashima.mp4 |video of the talk}}
+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.
-A string $s$ is called a parameterized square when $s = xy$ for strings $x$, $y$ and $x$ and $y$ are parameterized equivalent.
+**October 14 2025: [[https://www.nord.no/en/about/employees/antoine-laurent-christophe-julien|Antoine Julien]]** //On balance properties of hypercubic billiard words//
-Kociumaka et al. showed the number of parameterized squares, which are non-equivalent in parameterized equivalence, in a string of length $n$ that contains $\sigma$ distinct characters is at most $2 \sigma! n$ [TCS 2016].
-Recently, we showed that the maximum number of non-equivalent parameterized squares is less than $\sigma n$, which significantly improves the best-known upper bound by Kociumaka et al.
-This is a joint work with Rikuya Hamai, Kazushi Taketsugu, Shunsuke Inenaga, and Hideo Bannai (presented at SPIRE 2024).
+{{ seminar2025:20251014julien.pdf |slides}}
+{{ seminar2025:20251014julien.mp4 |video of the talk}}
-**December 3 2024: POSTPONED **
+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.
-**November 19 2024: [[https://www-lmpa.univ-littoral.fr/~lvivion/|Léo Vivion]]** //Balancedness constants of words generated by billiards in the hypercube//
+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é.
-{{ seminar2024:20241119vivion.pdf |slides}}
-A hypercubic billiard word in dimension $d$ is an infinite $d$-ary word encoding the faces successively hit by a billiard ball moving in the unit cub of $\mathbb{R}^d$, in which two parallel faces are labeled by the same letter. Square billiard words generated by a (billiard ball with an initial) momentum with rationally independent coordinates are Sturmian, so hypercubic billiard words generated by a momentum with rationally independent coordinates are one dynamical generalization of Sturmian words. Hence, it is natural to ask which properties satisfied by Sturmian words are still satisfied by hypercubic billiard words.
-While the subword complexity of hypercubic billiard words has been extensively studied at the end of the 1990s and the beginning of the 2000s (Arnoux, Mauduit, Shiokawa and Tamura 1994, Baryshnikov 1995 and Bédaride 2003-2009), their abelian properties have been much less studied: only Vuillon (2003) initiated the study of their balancedness.
+**September 16 2025: Kaisei Kishi** //Net Occurrences in Fibonacci and Thue-Morse Words//
-In this talk, I will first recall the results obtained by Vuillon, and then, give a complete characterization of the imbalance of hypercubic billiard words generated by a momentum with rationally independent coordinates. In a second part, I will also discuss the case of momenta with rationally dependent coordinates.
+{{ 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.
-**November 05 2024: [[https://www.lri.fr/~hellouin/|Benjamin Hellouin de Menibus]]** //String attractors for infinite words//
-{{ seminar2024:20241105hellouin.pdf |slides}}
+**September 2 2025: Gandhar Joshi** //Monochromatic Arithmetic Progressions in Sturmian sequences//
-{{ seminar2024:20241105hellouin.mp4 |video of the talk}}
+{{ 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.
-A string attractor of a word w is a set of marked positions such that every factor of w has an occurrence that crosses one of the marked positions. This is a recent concept whose motivation comes from the study of compression algorithms, but that was studied very soon after for its combinatorial properties. In particular, the size or span of the smallest string attractor for a word can be seen as a measure of its complexity, and this point of view led to studying smallest string attractors for families of classical words, such as the prefixes of the Fibonacci word.
-While it is fruitful to study smallest string attractors on finite prefixes or factors of infinite words, we can also define string attractors directly on infinite words. Unfortunately, there is no good notion of smallest string attractor in this setting, except when there is a finite one, which in the one-sided case means that the word is periodic.
+**July 15 2025: [[https://apacz.matinf.uj.edu.pl/users/1719-elzbieta-krawczyk|Elżbieta Krawczyk]]**  //Quasi-fixed points of substitutions and substitutive systems//
-Fortunately, the two-sided case is more rich in this regard, and is the topic of this talk. We study and completely characterise two-sided infinite words that admit a finite string attractor, and relate the size of the smallest attractor to their complexity function. We also get another characterisation of (quasi-)Sturmian words. I will also mention some side results regarding periodic string attractors and / or string attractors for shifts.
+{{ seminar2025:20250715krawczyk.pdf |slides}}
-This is a joint work with Pierre Béaur and France Gheeraert.
+{{ 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.
-**October 22 2024: [[https://www.irif.fr/~carton/|Olivier Carton]]** //Mahler  equations for Zeckendorf numeration//
-{{ seminar2024:20241022carton.pdf |slides}}
-{{ seminar2024:20241022carton.mp4 |video of the talk}}
+**June 17 2025: [[https://sites.google.com/view/noysofferaranov/bio|Noy Soffer Aranov]]** //Escape of Mass of Sequences//
+{{ seminar2025:20250617aranov.pdf |slides}}
-Let $U = (u_n)$ be a Pisot numeration system.  A sequence $(f_n)$ taking values
+{{ seminar2025:20250617aranov.mp4 |video of the talk}}
-over a commutative ring $R$, possibly infinite, is said to be //$U$-regular//
-if there exists a //weighted// automaton which outputs $f_n$ when it reads
-$(n)_U$.  For base-$q$ numeration, with $q ∈ ℕ$, $q$-regular sequences
-were introduced and studied by Allouche and Shallit, and they are a
-generalisation of $q$-automatic sequences $(f_n)$, where $f_n$ is the output of a
-deterministic automaton when it reads $(n)_q$.  Becker, and also Dumas, made
-the connection between $q$-regular sequences, and //$q$-Mahler type//
-equations. In particular a $q$-regular sequence gives a solution to an
-equation of $q$-Mahler type, and conversely, the solution of an
-//isolating//, or Becker, equation of $q$-Mahler type is $q$-regular.
-We define generalised equations of $Z$-Mahler type, based on the Zeckendorf
-numeration system $Z$. We show that if a sequence over a commutative ring is
-$Z$-regular, then it is the sequence of coefficients of a series which is a
-solution of a $Z$-Mahler equation. Conversely, if the $Z$-Mahler equation is
-isolating, then its solutions define $Z$-regular sequences.  We provide an
-example to show that there exist non-isolating $Z$-Mahler equations whose
-solutions do not define $Z$-regular sequences. Our proof yields a new
-construction of weighted automata that generate classical $q$-regular
-sequences.
-This is joint work with Reem Yassawi.
+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.
-**October 8 2024: [[https://scholar.google.com/citations?user=esm2VVoAAAAJ&hl=en|Mehdi Golafshan]]** //Factor complexity of the most significant digits and unipotent dynamics on a torus
-//
-{{ seminar2024:20241008golafshan.pdf |slides}}
+**June 3 2025: [[https://www.curtisbright.com/|Curtis Bright]]** //Mathematical Problems with SATisfying Solutions//
-{{ seminar2024:20241008golafshan.mp4 |video of the talk}}
+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}}
-In this talk, we explore the dynamics of unipotent flows on a torus and how these techniques lead to interesting applications in number theory. Specifically, I'll focus on the following problem: let \(d\) be a positive integer, and \(a > 0\) be a real number. Consider a square-free integer \(b \geqslant 5\) such that \(a\) and \(b\) are multiplicatively independent. We then examine the sequence \((\mathbf{w}_n)\), where \(\mathbf{w}_n\) represents the most significant digit of \(a^{n^d}\) when written in base \(b\). I will present our result, showing that the complexity function of this sequence, with only a finite number of exceptions, is a polynomial function. This work connects dynamics on homogeneous spaces with problems in symbolic dynamics and number theory, offering new insights into sequence complexity.
+{{ seminar2025:20250603bright.mp4 |video of the talk}}
-Based on a joint work with Ivan Mitrofanov: https://arxiv.org/abs/2402.16210
-**September 24 2024: [[http://lukeschaeffer.com/|Luke Schaeffer]]** //Summation and transduction of automatic sequences//
+**May 20 2025: [[https://www.researchgate.net/profile/Pranjal-Jain-10|Pranjal Jain]]** //Partial Sums of Binary Subword-Counting Sequences//
-{{ seminar2024:20240924schaeffer.pdf |slides}}
+{{ seminar2025:20250520jain.pdf |slides}}
-{{ seminar2024:20240924schaeffer.mp4 |video of the talk}}
+{{ seminar2025:20250520jain.mp4 |video of the talk}}
-We examine the theory of computing partial sums or transductions in automatic sequences, including a theorem of Dekking and its generalization. We give a number of examples involving paperfolding words and Sturmian sequences.
+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}}
-**September 10 2024: [[https://www.researchgate.net/scientific-contributions/Jia-Yan-Yao-81463053|Jia-Yan Yao]]** //When is an automatic number transparent?//
+{{ seminar2025:20250506peltomaki.mp4 |video of the talk}}
-{{ seminar2024:20240911yao.mp4 |video of the talk}}
-In this talk we introduce a new notion to
+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.
-measure the complexity of automatic numbers,
-which are either rational or transcendental.
-We study basic properties of this notion, and
- exhibit an algorithm to compute it. In particular,
-we shall characterize all the automatic numbers
-which are transparent. As applications, we shall
-also compute the  complexity of some well-known
-automatic numbers.
+Joint work with L. Mol and J. D. Currie.
-**July 9 2024: [[https://scholar.google.com.au/citations?user=C_02gXUAAAAJ&hl=en|Jamie Simpson]]** //Palindromic Periodicities//
-{{ seminar2024:20240709simpson.pdf |slides}}
+**April 22 2025: [[https://sites.google.com/view/beeri-greenfeld|Be'eri Greenfeld]]** //On the Complexity of Infinite Words//
-{{ seminar2024:20240709simpson.mp4 |video of the talk}}
-If $p$ and $s$ are palindromes then a factor of the infinite word $(ps)^\omega$ which has length at least $|ps|$ is called a palindromic periodicity.  In this talk I will first describe some simple properties of these objects and then show how they can appear.  For example a word which is both periodic and a palindrome is a palindromic periodicity. Next I'll present a periodicity lemma similar to the Fine Wilf Lemma but applied to palindromic periodicities.  The talk will finish with some suggestions for further research.
+{{ 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.
-**June 25 2024: [[http://iml.univ-mrs.fr/~cassaign/|Julien Cassaigne]]** //The Heinis Spectrum//
+Joint work with C. G. Moreira and E. Zelmanov.
-{{ seminar2024:20240625cassaigne.pdf |slides}}
-{{ seminar2024:20240625cassaigne.mp4 |video of the talk}}
+**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}}
-Many families of infinite words (or of subshifts) have a subword complexity
+{{ seminar2025:20250408kaneko.mp4 |video of the talk}}
-function $p(n)$ that grows linearly.  It has sometimes a very simple form
-(such as $n + 1$, $2n + 1$, etc.), but often a more complicated behaviour,
-as for the Thue-Morse word.  In his Ph.D. thesis, Alex Heinis introduced the
-set $\Omega$ of pairs $(\alpha,\beta)$ such that $\alpha = \liminf p(n)/n$
-and $\beta = \limsup p(n)/n$ for some infinite word.  For instance, the
-Thue-Morse word gives the point $(3, 10/3)$.  But not every point with
-$\alpha \leq \beta$ can be obtained, and it is a challenge to characterize
-points in $\Omega$.  We present some properties of this set, and some
-questions that we find interesting.
-**June 11 2024: [[https://mwhiteland.github.io/|Markus Whiteland]]**  //What I know about Parikh-collinear morphisms//
+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.
-{{ seminar2024:20240611whiteland.pdf |slides}}
+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.
-{{ seminar2024:20240611whiteland.mp4 |video of the talk}}
+**March 25 2025: [[https://page.mi.fu-berlin.de/vbui/|Vuong Bui]]** //An explicit condition for boundedly supermultiplicative subshifts//
-A morphism is Parikh-collinear if its adjacency matrix has rank at most one. For example, the famous Thue-Morse morphism is such morphism. Some of their properties have been considered in the literature, e.g., by Allouche et al. [Comb. Theory 1, 2021] (in passing) and Cassaigne et al. [Int. J. Found. Comput. 22, 2011]; the latter characterises Parikh-collinear morphisms as those morphisms that map any infinite word (over the domain alphabet) to a word with bounded abelian complexity.
-In this talk I will focus on properties of Parikh-collinear morphisms and their fixed points from the viewpoint of binomial complexities. We will also consider automatic (in the sense of Allouche and Shallit) aspects related to such fixed points.
+{{ seminar2025:20250325bui.pdf |slides}}
-The talk is based on joint work with M. Rigo and M. Stipulanti.
+{{ seminar2025:20250325bui.mp4 |video of the talk}}
-**May 28 2024: [[https://www.lirmm.fr/~ochem/|Pascal Ochem]]** //Characterization of morphic words.//
-{{ seminar2024:20240528ochem.pdf |slides}}
+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.
-{{ seminar2024:20240528ochem.mp4 |video of the talk}}
+**March 11 2025:[[https://www.irif.fr/users/letouzey/index|Pierre Letouzey]]** //Generalizing some Hofstadter functions: G, H and beyond//
+{{ seminar2025:20250311letouzey.pdf |slides}}
-The famous Hall-Thue word, fixed point of the morphism
+Hofstadter's G function is recursively defined via $G(0)=0$ and then
--> 012, 1 -> 02, 2 -> 1, is essentially the only infinite
+$G(n)=n-G(G(n-1))$. Following Hofstadter, a family $(F_k)$ of similar
-ternary word avoiding squares and the words 010 and 212.
+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.
-I will present many examples of this phenomenon, that is,
+Joint work with Shuo Li (U. Winnipeg) and Wolfgang Steiner (IRIF, Paris).
-when every recurrent word satisfying some avoidance constraints
-has the same factor set as a morphic word.
-This is a joint work with Golnaz Badkobeh, Matthieu Rosenfeld,
-L'ubomíra Dvořáková, Daniela Opočenská, Aseem Baranwal,
-James Currie, Lucas Mol, Narad Rampersad, and Jeffrey Shallit.
-**May 14 2024: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Restivo Salemi property for $\alpha$-power free languages with $\alpha \geq 5$ and $k \geq 3$ letters//
+**February 25 2025: [[https://ms.polsl.pl/pracownik.php?kod=pawl|Bartek Pawlik]]** //Words Avoiding Tangrams//
-{{ seminar2024:20240514rukavicka.pdf |slides}}
+{{ seminar2025:20250225pawlik.pdf |slides}}
-{{ seminar2024:20240514rukavicka.mp4 |video of the talk}}
+{{ seminar2025:20250225pawlik.mp4 |video of the talk}}
-In 2009, Shur published the following conjecture: Let $L$ be a power-free language and let $e(L)\subseteq L$ be the set of words of $L$ that can be extended to a bi-infinite word respecting the given power-freeness. If $u,v \in e(L)$ then $uwv \in e(L)$ for some word $w$. Let $L_{k,\alpha}$ denote an $\alpha$-power free language over an alphabet with $k$ letters, where $\alpha$ is a positive rational number and $k$ is positive integer. We prove the conjecture for the languages $L_{k,\alpha}$, where $\alpha\geq 5$ and $k \geq 3$.
+Work in collaboration with Michał Dębski, Jarosław Grytczuk, Jakub Przybyło and Małgorzata Śleszyńska-Nowak.
-https://arxiv.org/abs/2312.10061
+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.
-**April 30 2024: [[https://www.math.uni-bielefeld.de/baake/|Michael Baake]]** //Hats, CAPs and Spectres//
-{{ seminar2024:20240430baake.pdf |slides}}
+**February 11 2025: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Palindromic length of infinite aperiodic words//
-{{ seminar2024:20240430baake.mp4 |video of the talk}}
+{{ seminar2025:20250211rukavicka.pdf |slides}}
-The recently discovered Hat is an aperiodic
+{{ seminar2025:20250211rukavicka.mp4 |video of the talk}}
-monotile for the Euclidean plane, which needs a reflected
-version for this property. The Spectre does not have this
-(tiny) deficiency. We discuss the topological and dynamical
-properties of the Hat tiling, how the CAP relates to it, and
-what the long-range order of both tilings is. Finally, we
-briefly describe the analogous structure for the Spectre tiling.
+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.
-**April 16 2024: [[https://dblp.org/pid/215/5120.html|Radosław Piórkowski]]** //Universal quantification in automatic structures—an ExpSpace-hard nut to crack//
+Here is [[https://arxiv.org/abs/2410.12714|the paper]].
-{{ seminar2024:20240416piorkowski.mp4 |video of the talk}}
-Automatic structures are structures whose universe and relations can be represented as regular languages. It follows from the standard closure properties of regular languages that the first-order theory of an automatic structure is decidable.
-While existential quantifiers can be eliminated in linear time by application of a homomorphism, universal quantifiers are commonly eliminated via the identity ∀x. Φ ≡ ¬(∃x. ¬Φ). If Φ is represented in the standard way as an NFA, a priori this approach results in a doubly exponential blow-up. However, the recent literature has shown that there are classes of automatic structures for which universal quantifiers can be eliminated without this blow-up when treated as first-class citizens and not resorting to double complementation. The existing lower bounds for some classes of automatic structures show that a singly exponential blow-up is unavoidable when eliminating a universal quantifier, but it is not known whether there may be better approaches that avoid the naïve doubly exponential blow-up.
-We answer this question negatively.
-In my talk, following a short introduction to the field of automatic structures, I will present the construction of a family of NFA representing automatic relations for which the minimal NFA recognising the language after a universal projection step is doubly exponential, and deciding whether this language is empty is ExpSpace-complete.
+**January 28 2025: [[https://faculty.tru.ca/lmol/|Lucas Mol]]** //Avoiding abelian and additive powers in rich words//
-Based on the paper: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.13
+{{ seminar2025:20250128mol.pdf |slides}}
-Authors: Christoph Haase, R.P.
+{{ seminar2025:20250128mol.mp4 |video of the talk}}
-Keywords: automatic structures, universal projection, tiling problems, state complexity.
+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.
-**April 2 2024: John Campbell** // On the evaluation of infinite products involving automatic sequences//
-{{ seminar2024:20240402campbell.pdf |slides}}
-{{ seminar2024:20240402campbell.mp4 |video of the talk}}
+**January 14 2025: [[https://reutenauer.math.uqam.ca|Christophe Reutenauer]]** //Christoffel matrices and Sturmian determinants//
-We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences.
+{{ 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)
-**March 19 2024: [[https://diamweb.ewi.tudelft.nl/~cork/|Cor Kraaikamp]]** //An introduction to $N$-expansions with a finite set of digits//
+. The determinant of a Christoffel matrix has a simple form, using the Zolotareff symbol (the latter extends the Jacobi symbol).
-{{ seminar2024:20240319kraaikamp.pdf |slides}}
+. 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.
-{{ seminar2024:20240319kraaikamp.mp4 |video of the talk}}
-In this talk $N$-expansions, and in particular $N$-expansions with a finite set
-of digits, will be introduced. Although $N$-expansions were introduced as
-recent as 2008 by Ed Burger and some of his students, quite a number of
-papers have appeared on these variations of the regular continued fraction
-expansion. By choosing a domain for the underlying Gauss-map which does
-not contain the origin, a continued fraction with finitely many digits was
-introduced by Niels Langeveld in his MSc-thesis. It turns out that these
-continued fraction algorithms exhibit a very complicated and surprising rich
-dynamical behavior.
-This talk is based on joint work with Yufei Chen (Shanghai, Delft), Jaap
-de Jonge (UvA, Amsterdam), Karma Dajani (Utrecht), Niels Langeveld
-(Montan U., Leoben), Hitoshi Nakada (Keio, Yokohama), and Niels van der
-Wekken (Netcompany).
-**March 5 2024: [[https://finnlidbetter.com/|Finn Lidbetter]]** //Improved bound for the Gerver-Ramsey collinearity problem//
-{{ seminar2024:20240305lidbetter.pdf |slides}}
-{{ seminar2024:20240305lidbetter.mp4 |video of the talk}}
-Let $S$ be a finite subset of $\mathbb{Z}^n$. A vector
-sequence $(z_i)$ is an $S$-walk if and only if $z_{i+1}-z_i$ is an
-element of $S$ for all $i$. Gerver and Ramsey showed in 1979 that for
-$S\subset\mathbb{Z}^3$ there exists an infinite $S$-walk in which no
-$5^{11}+1=48,828,126$ points are collinear. Using the same general
-approach, but with the aid of a computer search, we show how to
-improve the bound to $189$. We begin by restating the infinite
-$S$-walk as the fixed point of iterating a morphism defined for a $12$
-letter alphabet.
-**February 20 2024: [[https://www.uliege.be/cms/c_9054334/fr/repertoire?uid=u240328|Christopher Cabezas]]** //Large normalizer of odometers and higher-dimensional automatic sequences//
-{{ seminar2024:20240220cabezas.pdf |slides}}
-{{ seminar2024:20240220cabezas.mp4 |video of the talk}}
-For a $\mathbb Z^d$ topological dynamical system $(X, T, \mathbb Z^d)$, an isomorphism is a self-homeomorphism $\phi : X\to X$ such that for some matrix $M \in GL(d, \mathbb Z)$ and any $n \in \mathbb Z^d$, $\phi \circ T^n = T^{M_n} \circ \phi$, where $T^n$ denote the self-homeomorphism of $X$ given by the action of $n \in \mathbb Z^d$. The collection of all the isomorphisms forms a group that is the normalizer of the set of transformations $T^n$. In the one-dimensional case isomorphisms correspond to the notion of flip conjugacy of dynamical systems and by this fact are also called reversing symmetries.
-These isomorphisms are not well understood even for classical systems. In this talk we will present a description of them for odometers and more precisely for $\mathbb Z^2$-constant base odometers, that is not simple. We deduce a complete description of the isomorphism of some $\mathbb Z^2$ minimal substitution subshifts. Thanks to this, we will give the first known example of a minimal zero-entropy subshift with the largest possible normalizer group.
-This is a joint work with Samuel Petite (Universitè de Picardie Jules Verne).
-**February 6 2024: [[https://ericrowland.github.io/|Eric Rowland]]** //Algebraic power series and their automatic complexity//
-{{ seminar2024:20240206rowland.pdf |slides}}
-{{ seminar2024:20240206rowland.mp4 |video of the talk}}
-A theorem of Christol gives a characterization of automatic sequences over a finite field: a sequence is automatic if and only if its generating series is algebraic. Since there are two representations for such a sequence -- as an automaton and as a bivariate polynomial -- a natural question is how the size of one representation relates to the size of the other. Bridy used tools from algebraic geometry to bound the size of the minimal automaton in terms of the size of the minimal polynomial. We have a new proof of Bridy's bound that works by converting algebraic sequences to diagonals of rational functions. Crucially for our interests, this approach can be adapted to work not just over a finite field but over the integers modulo a prime power. This is joint work with Manon Stipulanti and Reem Yassawi.
-**January 23 2024: [[https://jakubmichalkonieczny.wordpress.com/|Jakub Konieczny]]** //Arithmetical subword complexity of automatic sequences//
-{{ seminar2024:20240123konieczny.pdf |slides}}
-{{ seminar2024:20240123konieczny.mp4 |video of the talk}}
-It is well-known that the subword complexity of an automatic sequence grows at most linearly, meaning that the number of length-$\ell$ subwords which appear in a given automatic sequence $a = (a(n))_n$ is at most $C \ell$ for a constant $C$ dependent only on $a$. In contrast, arithmetic subword complexity measures the number of subwords which appear along arithmetic progressions, and can grow exponentially even for very simple automatic sequences. Indeed, the classical Thue-Morse sequence has arithmetic subword complexity $2^{\ell}$, which is the maximal possible complexity for $\{0,1\}$-valued sequence.
-Together with Jakub Byszewski and Clemens Müllner we obtained a decomposition result which allows us to express any (complex-valued) automatic sequence as the sum of a structured part, which is easy to work with, and a part which is pseudorandom or uniform from the point of view of higher order Fourier analysis. We now apply these techniques to the study of arithmetic subword complexity of automatic sequences. We show that for each automatic sequence $a$ there exists a parameter $r$ --- which we dub "effective alphabet size" --- such that the arithmetic subword complexity of $a$ is at least $r^{\ell}$ and at most $(r+o(1))^{\ell}$.
-This talk is based on joint work with Jakub Byszewski and Clemens Müllner, and is closely related to the previous talk of Clemens Müllner at One World Combinatorics on Words Seminar.
-**January 9 2024: [[https://dmg.tuwien.ac.at/cmuellner/|Clemens Müllner]]** //Synchronizing automatic sequences along Piatetski-Shapiro sequences//
-{{ seminar2024:20240109muellner.pdf |slides}}
-{{ seminar2024:20240109muellner.mp4 |video of the talk}}
-Automatic sequences - that is, sequences computable by finite automata - have long been studied from the point of view of combinatorics on words. A notable property of these sequences is that their subword-complexity is at most linear. Avgustinovich, Fon-Der-Flaass and Frid introduced the notion of arithmetic subword-complexity - that is the number of different subwords of length $n$ that appear along some arithmetic progression.
-They also showed that a special class of synchronizing automatic sequences have at most linear arithmetic subword-complexity and some other class of automatic sequences on the alphabet $\Sigma$ have maximal possible subword-complexity $|\Sigma|^n$.
-Synchronizing automatic sequences can be efficiently approximated using periodic functions and are usually more structured than general automatic sequences. We discuss a recent result showing that the arithmetic (and even polynomial) subword-complexity of synchronizing automatic sequences grows subexponentially. This was a key result to show that the subword-complexity of synchronizing automatic sequences along regularly growing sequences (such as Piatetski-Shapiro sequences) grows subexponentially, which is in stark contrast to other automatic sequences such as the Thue-Morse sequence. Moreover, this was a key ingredient to obtain rather precise estimates for the arithmetic (and polynomial) subword-complexity of general automatic sequences.
-This is joint work with Jean-Marc Deshouillers, Michael Drmota, Andrei Shubin and Lukas Spiegelhofer.
 ==== Archives 2024 ====
-The talks of 2023 are available [[2024|here]].
+The talks of 2024 are available [[2024|here]].
 ==== Archives 2023 ====