One World Combinatorics on Words Seminar

The seminar takes place biweekly on Mondays at 15:00 CET. In winter, it means 6:00 in California, 9:00 in New-York or Waterloo, 14:00 in London, 15:00 in Paris, 17:00 in Moscow and 23:00 in Tokyo.

URL

The address of the Zoom meeting is https://zoom.us/j/92245493528 . The password is distributed in announcements. If you want to receive them, or receive them and want to unsubscribe, please write to Anna Frid.

All recorded talks are also available here.

Organizers:

Anna E. Frid, Aix-Marseille Université, Narad Rampersad, University of Winnipeg, Jeffrey O. Shallit, University of Waterloo, Manon Stipulanti, Université de Liège.

If you are interested in giving a talk, you are welcome to contact Narad Rampersad and Manon Stipulanti.

Day of short talks February 22, 2021

This mini-event is designed to take the place of a small and very informal conference in our field, since many of us miss direct communication of this kind.

The event will consist of short talks in 25-minute slots, including your new results, discussions, and open questions. If you are interested in giving such a talk, please send your title and abstract to Anna Frid (anna.e.frid@gmail.com) as soon as possible.

The abstracts (with eventual references to arxiv.org), slides and some videos of talks will be published at this page.

Deadline for submissions: January 24, 2021

Upcoming talks

1 February 2021: Jean-Paul Allouche Hidden automatic sequences

We discuss a joint work with Michel Dekking and Martine Queffélec (https://arxiv.org/abs/2010.00920) about sequences given as fixed points of non-uniform morphisms that happen to be actually automatic.

One of the most ancien example is probably the one due to Berstel, who proved that the Istrail squarefree sequence defined as the fixed point of the morphism $f$ with $f(0) = 12$, $f(1) = 102$, $f(2) = 0$ is also $2$-automatic.

After revisiting an old criterion due to M. Dekking at the end of the 70's, we give several examples (in particular of sequences in the OEIS). Finally we focus on morphisms associated with Grigorchuk(-like) groups.

8 February 2021: Robert Mercas (Trying to do a) Counting of distinct repetitions in words

The topic of counting the distinct repetitions that a word contains has been around for at least two decades. The problem of counting distinct squares in a word was introduced by Fraenkel and Simpson in ’98, who also showed that their number is upper bounded by twice the length of the word. However, their conjecture that the factor of 2 is superfluous (the length of the word is a strict bound) is still open (though there exist several improvements of their original result). Moreover, recently Manea and Seki showed that proving the bound for binary words is enough. Moreover, further work was done on counting distinct repetitions of higher exponent with quite sharp bounds. By looking at non-extendable repetitions of power at least two (thus considering fractional ones as well) Kolpakov and Kucherov tried to bound in ‘99 the number of runs in a word (non-necessarily distinct). This was recently shown to be less than the length $n$ of the word that we consider and more than 0.9482 times $n$. However, all of these ideas have a common sticking point, namely the three squares lemma of Crochemore and Rytter, which they all use as main tool. In this talk I will present a different technique (which so far is not fully exploited) of trying to count distinct squares and show some surprising connections between all of the above notions.

15 February 2021: Petr Ambrož

22 February 2021: Day of Short Talks

Interested speakers include:

  • Mélodie Andrieu A Rauzy fractal unbounded in all directions of the plane
  • Célia Cisternino Two applications of the composition of a $2$-tape automaton and a weighted automaton
  • Francesco Dolce On morphisms preserving palindromic richness
  • Lubka Dvořáková On balanced sequences with the minimal asymptotic critical exponent
  • Anna Frid The semigroup of trimmed morphisms
  • Štěpán Holub Formalization of Combinatorics on Words in Isabelle/HOL
  • Florin Manea Efficiently Testing Simon's Congruence
  • Christophe Reutenauer An arithmetical characterization of Christoffel words
  • Jeffrey Shallit Robbins and Ardila meet Berstel

1 March 2021: Mickaël Postic

15 March 2021: Szymon Stankiewicz

29 March 2021: Jacques Sakarovitch

12 April 2021: Valérie Goyheneche

26 April 2021: Luca Zamboni

Past talks

4 January 2021: Anna Frid Is not prefix palindromic length of a $k$-automatic word $k$-regular?

slides

We consider the function of the prefix palindromic length for $k$-automatic words and prove that it is $k$-regular for such words containing a finite number of distinct palindromes, like for example the paperfolding word. We also observe that in the opposite case, if the number of distinct palindromes is infinite, this function can be $k$-regular, as for the Thue-Morse word, or seemingly not, as for the period-doubling word. The fact of non-regularity, however, stays unproven.

This is a joint work with Enzo Laborde and Jarkko Peltomäki. The preprint is available at https://arxiv.org/abs/2009.02934.

14 December 2020: Sébastien Labbé A characterization of Sturmian sequences by indistinguishable asymptotic pairs

slides

We give a new characterization of Sturmian configurations in terms of indistinguishable asymptotic pairs. Two asymptotic configurations on a full $\mathbb{Z}$-shift are indistinguishable if the sets of occurrences of every pattern in each configuration coincide up to a finitely supported permutation. This characterization can be seen as an extension to biinfinite sequences of Pirillo's theorem which characterizes Christoffel words. Furthermore, we provide a full characterization of indistinguishable asymptotic pairs on arbitrary alphabets using substitutions and characteristic Sturmian sequences. The proof is based on the well-known notion of derived sequences.

This is joint work with Sebastián Barbieri and Štěpán Starosta. Preprint is available at https://arxiv.org/abs/2011.08112

7 December 2020: Marie Lejeune Reconstructing words from right-bounded-block words

slides

In this joint work with P. Fleischmann, F. Manea, D. Nowotka, and M. Rigo, we study a variation of the famous reconstruction problem over words. It has been studied since $1973$. A survey of the different results will be held in the talk.

We study a variation of this problem. Let $\mathcal{A}$ be a given alphabet and $n$ a natural number. We want to reconstruct a hidden word $w \in \mathcal{A}^n$. To that aim, we are allowed to pick a word $u_i$ and ask questions of the type “What is the multiplicity of $u_i$ as subword of $w$?”. Based on the answers to questions related to words $u_1, \ldots, u_i$, we can decide which will be the next question (i.e. decide which word will be $u_{i+1}$). We want to have the shortest sequence $(u_1, \ldots, u_k)$ uniquely determining $w$.

We naturally look for a value of $k$ less than the upper known bound for $k$-reconstructibility.

We will show how to reconstruct a binary word $w$ from $m+1$ questions, where $m$ is the minimum number of occurrences of a and b in the word. We then reduce the problem for arbitrary finite alphabets to the binary case. We compare our bounds to the best known one for the classical reconstruction problem.

23 November 2020: Émilie Charlier Regular sequences in abstract numeration systems

slides

An abstract numeration system $S$ is given by a regular language $L$ over a totally ordered alphabet $(A,<)$. The numeration language $L$ is ordered thanks to the radix (or genealogical) order induced by $<$. A natural number $n$ is then represented by the $n$-th word of the language (where we start counting from $n=0$). Integer bases $b$ and numeration systems based on a linear base sequence $U$ with a regular numeration language are examples of abstract numeration systems. The notion of $b$-regular sequences was extended to abstract numeration systems by Maes and Rigo. Their definition is based on a notion of $S$-kernel that extends that of $b$-kernel. However, this definition does not allow us to generalize all of the many characterizations of $b$-regular sequences. In this talk, I will present an alternative definition of $S$-kernel, and hence an alternative definition of $S$-regular sequences, that permits us to use recognizable formal series in order to generalize most (if not all) known characterizations of $b$-regular sequences. I will also show that an extra characterization can be obtained in the case of Pisot numeration systems. Finally, I will consider the special cases of $S$-automatic and $S$-synchronized sequences. In particular, we will see that the factor complexity of an $S$-automatic sequence defines an $S$-regular sequence. This is a joint work with Célia Cisternino and Manon Stipulanti.

9 November 2020: Eric Rowland Avoiding fractional powers on an infinite alphabet

slides

Questions concerning avoidability of patterns have been central to combinatorics on words since the work of Thue. In 2009, Guay-Paquet and Shallit gave several results about pattern avoidance of words on the alphabet of natural numbers. Most patterns are avoidable on this alphabet, but it is interesting to ask about the lexicographically least word that avoids a pattern. For fractional powers, often this word is generated by a relatively simple morphism. In recent work with Manon Stipulanti, we discovered the structure of the lexicographically least $5/4$-power-free word on the natural numbers. In a surprising departure from previously studied words, the morphism generating this word does not preserve $5/4$-power-freeness.

26 October 2020: Matthieu Rosenfeld A simple proof technique to study avoidability of repetitions

slides

I recently described a new proof technique that I used to study nonrepetitive colorings of graphs. This technique is in fact more general and seems to be as powerful as the Lovász local lemma or the entropy compression method. For instance, it has since been used by D.R. Wood and I.M. Wanless in the context of boolean satisfiability problem and of hypergraph colorings. In the particular context of combinatorics on words similar approaches had already been used by different authors, but were never extended to graphs or other structures.

In this talk, I will first present some simple applications of the method to combinatorics on words and I will then explain how to extend this approach to nonrepetitive colorings of graphs of bounded degree.

19 October 2020: Michel Dekking The structure of Zeckendorf representations and base $\varphi$ expansions

slides

In the Zeckendorf numeration system natural numbers are represented as sums of Fibonacci numbers. In base $\varphi$ natural numbers are represented as sums of powers of the golden mean $\varphi$. Both representations have digits 0 and 1, where the word 11 is not allowed. We know that the Fibonacci numbers, and the powers of $\varphi$ are closely related, as, for example, in the relation $\varphi^n=F_{n-1}+F_n\varphi$. In fact, Frougny and Sakarovitch have shown that Zeckendorf representations can be transformed to base $\varphi$ expansions by a 2-tape automaton. I will take a direct approach: what are the words that can occur in the Zeckendorf representations, and what are those that occur in base $\varphi$ expansions? In which representations/expansions, of which natural numbers do they occur?

5 October 2020: Jarosław Grytczuk Graph Coloring and Combinatorics on Words

slides

I will present a few problems inspired mutually by various issues studied in the two disciplines of the title. For instance, given any sequence of 3-letter alphabets, is it possible to pick a letter from each alphabet so that the resulting word is square-free? The case of equal alphabets is covered by the famous result of Thue, but intuition tells us that this should be the hardest case (the more different letters in the play, the easier to avoid repeated factors). While more than one has attacked the problem, the question remains unanswered, which is especially frustrating as it has a positive answer with 4-letter alphabets. The above question was originally motivated by the list coloring problem, a very popular topic in graph coloring. However, the opposite direction of inspiration also leads to intriguing matters. For example, how many letters are needed to label the vertices of a planar graph so that any word occurring along a simple path is square-free? It has been recently proved that 768 letters suffice, but for a long time it was not known if any finite alphabet will do. Perhaps results of that type could be applied back to some pattern avoidability issues…?

28 September 2020: Jarkko Peltomäki Avoiding abelian powers cyclically

slides

Sorry, the video of the talk was not recorded

A finite word $w$ avoids abelian $N$-powers cyclically if for each abelian $N$-power of period $m$, we have $m \geq |w|$. This notion generalizes circular avoidance of $N$-powers in two ways. Firstly “power” is replaced by “abelian power” and secondly circular avoidance concerns only the conjugacy class of a word, but here we require even more. Let $\mathcal{A}(k)$ be the least integer $N$ such that for all $n$ there exists a word of length $n$ over a $k$-letter alphabet that avoids abelian $N$-powers cyclically. Let $\mathcal{A}_\infty(k)$ be the least integer $N$ such that there exist arbitrarily long words over a $k$-letter alphabet that avoid abelian $N$-powers cyclically.

I will sketch the proofs of the following results: 1) $5 \leq \mathcal{A}(2) \leq 8$, $3 \leq \mathcal{A}(3) \leq 4$, $2 \leq \mathcal{A}(4) \leq 3$, $\mathcal{A}(k) = 2$ for $k \geq 5$; 2) $\mathcal{A}_\infty(2) = 4$, $\mathcal{A}_\infty(3) = 3$, and $\mathcal{A}_\infty(4) = 2$. If time permits, I will discuss an application to the growth rates of exponents of abelian powers occurring in infinite binary words.

14 September 2020: Reem Yassawi The Ellis semigroup of bijective substitution shifts abstract

slides

27 July 2020 - James Currie, Remarks on Pansiot encodings

slides

Pansiot encodings were an essential ingredient in the solution of Dejean's conjecture. We discuss these encodings, and the related group theoretic notions, in a way perhaps more natural to combinatorics on words, namely, in terms of De Bruijn graphs. We discuss variations on Pansiot encodings, with applications to circular words, and to the undirected threshold problem.

20 July 2020 - Laurent Vuillon, Combinatorics on words for Markoff numbers (joint work with Christophe Reutenauer) paper

slides

Markoff numbers are fascinating integers related to number theory, Diophantine equation, hyperbolic geometry, continued fractions and Christoffel words. Many great mathematicians have worked on these numbers and the $100$ years famous uniqueness conjecture by Frobenius is still unsolved. In this talk, we state a new formula to compute the Markoff numbers using iterated palindromic closure and the Thue-Morse substitution. The main theorem shows that for each Markoff number $m$, there exists a word $v\in \{a,b\}^*$ such that $m-2$ is equal to the length of the iterated palindromic closure of the iterated antipalindromic closure of the word $av$. This construction gives a new recursive construction of the Markoff numbers by the lengths of the words involved in the palindromic closure.

13 July 2020 - Michel Rigo Binomial$^3$ : coefficients, equivalence, complexity…

slides

The binomial coefficient $x \choose y$ of the words $x$ and $y$ is the number of times $y$ appears as a (scattered) subword of $x$. This concept has received a lot of attention, e.g., Simon's congruence, Parikh matrices, reconstruction problem, … A few years ago, we introduced the $k$-binomial equivalence: Two words $u$ and $v$ are $k$-binomially equivalent if the binomial coefficients $u \choose x$ and $v \choose x$ agree for all words $x$ of length up to $k$. This is a refinement of the usual abelian equivalence.

First, I will review several results (joint work with P. Salimov, M. Lejeune, J. Leroy, M. Rosenfeld) related to $k$-binomial complexity (where factors of length $n$ are counted up to $k$-binomial equivalence) for Sturmian words, Thue-Morse word and Tribonacci word. Then I will concentrate on $k$-binomial equivalence classes for finite words. In particular, I will discuss the fact that the submonoid generated by the generators of the free nil-$2$ group on $m$ generators is isomorphic to the quotient of the free monoid $\{1,\ldots,m\}^∗$ by the $2$-binomial equivalence (joint work with M. Lejeune, M. Rosenfeld).

29 June 2020 - Lucas Mol, Extremal Square-Free Words and Variations (joint work with Narad Rampersad and Jeffrey Shallit)

slides

A square-free word $w$ over a fixed alphabet $\Sigma$ is extremal if every word obtained from $w$ by inserting a single letter from $\Sigma$ (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word, and demonstrated that there are arbitrarily long extremal square-free words over a ternary alphabet. One can define extremal overlap-free words, and more generally, extremal $\beta$-free words, analogously. We characterize the lengths of extremal square-free ternary words, and the lengths of extremal overlap-free binary words. We also establish that there are arbitrarily long extremal $\beta$-free binary words for every $2 < \beta \leq 8/3$. We include a variety of interesting conjectures and open questions.

Lectures on combinatorics on words

Several starting lectures by Anna Frid are available here.

  • start.txt
  • Last modified: 2021/01/19 13:38
  • by anna.frid