Combinatorics on Words seminar

Upcoming talks

December 3 2024: Elżbieta Krawczyk

December 17 2024: Yuto Nakashima

January 14 2024: Christophe Reutenauer

January 28 2025: Jonathan Andrade/Lucas Mol

February 11 2025: Josef Rukavicka

February 25 2025: Bartek Pawlik

March 11 2025: Curtis Bright

March 25 2025: Vuong Bui

April 8 2025: Hajime Kaneko

April 22 2025: Be'eri Greenfeld

May 6 2025: Jarkko Peltomäki

Past talks 2024

November 19 2024: Léo Vivion Balancedness constants of words generated by billiards in the hypercube

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.

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.

November 05 2024: Benjamin Hellouin de Menibus String attractors for infinite words

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.

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.

This is a joint work with Pierre Béaur and France Gheeraert.

October 22 2024: Olivier Carton Mahler equations for Zeckendorf numeration

slides

Let $U = (u_n)$ be a Pisot numeration system. A sequence $(f_n)$ taking values 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.

October 8 2024: Mehdi Golafshan Factor complexity of the most significant digits and unipotent dynamics on a torus

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.

Based on a joint work with Ivan Mitrofanov: https://arxiv.org/abs/2402.16210

September 24 2024: Luke Schaeffer Summation and transduction of automatic sequences

slides

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.

September 10 2024: Jia-Yan Yao When is an automatic number transparent?

In this talk we introduce a new notion to 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: Jamie Simpson Palindromic Periodicities

slides

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: Julien Cassaigne The Heinis Spectrum

slides

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: Markus Whiteland What I know about Parikh-collinear morphisms

slides

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: Pascal Ochem Characterization of morphic words.

slides

The famous Hall-Thue word, fixed point of the morphism 0 → 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: Josef Rukavicka Restivo Salemi property for $\alpha$-power free languages with $\alpha \geq 5$ and $k \geq 3$ letters

slides

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: Michael Baake Hats, CAPs and Spectres

slides

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: Radosław Piórkowski Universal quantification in automatic structures—an ExpSpace-hard nut to crack

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

slides

We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences.

March 19 2024: Cor Kraaikamp An introduction to $N$-expansions with a finite set of digits

slides

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: Finn Lidbetter Improved bound for the Gerver-Ramsey collinearity problem

slides

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: Christopher Cabezas Large normalizer of odometers and higher-dimensional automatic sequences

slides

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: Eric Rowland Algebraic power series and their automatic complexity

slides

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: Jakub Konieczny Arithmetical subword complexity of automatic sequences

slides

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: Clemens Müllner Synchronizing automatic sequences along Piatetski-Shapiro sequences

slides

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 2023

The talks of 2023 are available here.

Archives 2022

The talks of 2022 are available here.

Archives 2021

The talks of 2021 are available here.

Archives 2020

The talks of 2020 are available here.

Lectures on combinatorics on words

Several starting lectures by Anna Frid are available here.

One World Combinatorics on Words Seminar

Table of Contents

One World Combinatorics on Words Seminar

URL

Organizers:

Upcoming talks

Past talks 2024

Archives 2023

Archives 2022

Archives 2021

Archives 2020

Lectures on combinatorics on words