Differences

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

--- start [2025/01/28 12:04] – 139.124.146.3
+++ start [2025/04/22 14:24] (current) – 139.124.146.3
@@ 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 22: / Line 22: @@
 ==== Upcoming talks ====
-**January 28 2025: [[https://faculty.tru.ca/lmol/|Lucas Mol]]** //Avoiding abelian and additive powers in rich words//
-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.
-**February 11 2025: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Palindromic length of infinite aperiodic words//
-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]].
-**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
-$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).
-**March 25 2025: Vuong Bui**
-**April 8 2025: Hajime Kaneko**
-**April 22 2025: Be'eri Greenfeld**
 **May 6 2025: Jarkko Peltomäki**
@@ Line 80: / Line 39: @@
 ==== Past talks 2025 ====
-**January 14 2025: [[https://reutenauer.math.uqam.ca|Christophe Reutenauer]]** //Christoffel matrices and Sturmian determinants//
+**April 22 2025: [[https://sites.google.com/view/beeri-greenfeld|Be'eri Greenfeld]]** //On the Complexity of Infinite Words//
-{{ seminar2025:20250114reutenauer.mp4 |video of the talk}}
+{{ seminar2025:20250422greenfeld.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)$.
+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.
-(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).
+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.
-. 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.
+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//
-==== Past talks 2024 ====
+{{ seminar2025:20250408kaneko.pdf |slides}}
-**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}}
+{{ seminar2025:20250408kaneko.mp4 |video of the talk}}
-{{ seminar2024:20241217nakashima.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.
-A string $s$ is called a parameterized square when $s = xy$ for strings $x$, $y$ and $x$ and $y$ are parameterized equivalent.
-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).
+**March 25 2025: [[https://page.mi.fu-berlin.de/vbui/|Vuong Bui]]** //An explicit condition for boundedly supermultiplicative subshifts//
+{{ seminar2025:20250325bui.pdf |slides}}
-**December 3 2024: POSTPONED **
+{{ seminar2025:20250325bui.mp4 |video of the talk}}
-**November 19 2024: [[https://www-lmpa.univ-littoral.fr/~lvivion/|Léo Vivion]]** //Balancedness constants of words generated by billiards in the hypercube//
-{{ 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.
+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.
-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.
-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.
+**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.
-**November 05 2024: [[https://www.lri.fr/~hellouin/|Benjamin Hellouin de Menibus]]** //String attractors for infinite words//
+Joint work with Shuo Li (U. Winnipeg) and Wolfgang Steiner (IRIF, Paris).
-{{ seminar2024:20241105hellouin.pdf |slides}}
-{{ seminar2024:20241105hellouin.mp4 |video of the talk}}
+**February 25 2025: [[https://ms.polsl.pl/pracownik.php?kod=pawl|Bartek Pawlik]]** //Words Avoiding Tangrams//
+{{ seminar2025:20250225pawlik.pdf |slides}}
-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.
+{{ seminar2025:20250225pawlik.mp4 |video of the talk}}
-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.
-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.
+Work in collaboration with Michał Dębski, Jarosław Grytczuk, Jakub Przybyło and Małgorzata Śleszyńska-Nowak.
-This is a joint work with Pierre Béaur and France Gheeraert.
+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.
-**October 22 2024: [[https://www.irif.fr/~carton/|Olivier Carton]]** //Mahler  equations for Zeckendorf numeration//
+**February 11 2025: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Palindromic length of infinite aperiodic words//
-{{ seminar2024:20241022carton.pdf |slides}}
+{{ seminar2025:20250211rukavicka.pdf |slides}}
-{{ seminar2024:20241022carton.mp4 |video of the talk}}
+{{ seminar2025:20250211rukavicka.mp4 |video of the talk}}
-Let $U = (u_n)$ be a Pisot numeration system.  A sequence $(f_n)$ taking values
+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.
-over a commutative ring $R$, possibly infinite, is said to be //$U$-regular//
+We prove this conjecture to be true.
-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
+Here is [[https://arxiv.org/abs/2410.12714|the paper]].
-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.
-**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}}
-{{ seminar2024:20241008golafshan.mp4 |video of the talk}}
+**January 28 2025: [[https://faculty.tru.ca/lmol/|Lucas Mol]]** //Avoiding abelian and additive powers in rich words//
-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:20250128mol.pdf |slides}}
-Based on a joint work with Ivan Mitrofanov: https://arxiv.org/abs/2402.16210
+{{ seminar2025:20250128mol.mp4 |video of the talk}}
-**September 24 2024: [[http://lukeschaeffer.com/|Luke Schaeffer]]** //Summation and transduction of automatic sequences//
-{{ seminar2024:20240924schaeffer.pdf |slides}}
+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.
-{{ seminar2024:20240924schaeffer.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.
+**January 14 2025: [[https://reutenauer.math.uqam.ca|Christophe Reutenauer]]** //Christoffel matrices and Sturmian determinants//
+{{ seminar2025:20250114reutenauer.mp4 |video of the talk}}
+Work in collaboration with Jeffrey Shallit.
-**September 10 2024: [[https://www.researchgate.net/scientific-contributions/Jia-Yan-Yao-81463053|Jia-Yan Yao]]** //When is an automatic number transparent?//
+. 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)
-{{ seminar2024:20240911yao.mp4 |video of the talk}}
+. The determinant of a Christoffel matrix has a simple form, using the Zolotareff symbol (the latter extends the Jacobi symbol).
-In this talk we introduce a new notion to
+. 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.
-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.
-**July 9 2024: [[https://scholar.google.com.au/citations?user=C_02gXUAAAAJ&hl=en|Jamie Simpson]]** //Palindromic Periodicities//
-{{ seminar2024:20240709simpson.pdf |slides}}
-{{ 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.
-**June 25 2024: [[http://iml.univ-mrs.fr/~cassaign/|Julien Cassaigne]]** //The Heinis Spectrum//
-{{ seminar2024:20240625cassaigne.pdf |slides}}
-{{ seminar2024:20240625cassaigne.mp4 |video of the talk}}
-Many families of infinite words (or of subshifts) have a subword complexity
-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//
-{{ seminar2024:20240611whiteland.pdf |slides}}
-{{ seminar2024:20240611whiteland.mp4 |video of the talk}}
-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.
-The talk is based on joint work with M. Rigo and M. Stipulanti.
-**May 28 2024: [[https://www.lirmm.fr/~ochem/|Pascal Ochem]]** //Characterization of morphic words.//
-{{ seminar2024:20240528ochem.pdf |slides}}
-{{ seminar2024:20240528ochem.mp4 |video of the talk}}
-The famous Hall-Thue word, fixed point of the morphism
--> 012, 1 -> 02, 2 -> 1, is essentially the only infinite
-ternary word avoiding squares and the words 010 and 212.
-I will present many examples of this phenomenon, that is,
-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//
-{{ seminar2024:20240514rukavicka.pdf |slides}}
-{{ seminar2024:20240514rukavicka.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$.
-https://arxiv.org/abs/2312.10061
-**April 30 2024: [[https://www.math.uni-bielefeld.de/baake/|Michael Baake]]** //Hats, CAPs and Spectres//
-{{ seminar2024:20240430baake.pdf |slides}}
-{{ seminar2024:20240430baake.mp4 |video of the talk}}
-The recently discovered Hat is an aperiodic
-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.
-**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//
-{{ 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.
-Based on the paper: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.13
-Authors: Christoph Haase, R.P.
-Keywords: automatic structures, universal projection, tiling problems, state complexity.
-**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}}
-We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences.
-**March 19 2024: [[https://diamweb.ewi.tudelft.nl/~cork/|Cor Kraaikamp]]** //An introduction to $N$-expansions with a finite set of digits//
-{{ seminar2024:20240319kraaikamp.pdf |slides}}
-{{ 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.
+==== Archives 2024 ====
-This is joint work with Jean-Marc Deshouillers, Michael Drmota, Andrei Shubin and Lukas Spiegelhofer.
+The talks of 2023 are available [[2024|here]].
 ==== Archives 2023 ====