Day of Short Talks on Combinatorics on Words, March 22, 2021

This second mini-event, organized by One World Combinatorics on Words Seminar, 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 page of the first Day of short talks is here.

The event consisted of short talks in 25-minute slots, including your new results, discussions, and open questions.

The deadline for submissions was January 24, 2021.

15:00 Jane D. Palacio Coverable bi-infinite substitution shifts


A finite or infinite word $w$ is said to be coverable if it can be formed by overlapping or adjacent occurrences of some finite subword $u$ of $w$. Coverability of finite words was introduced by A. Apostolico and A. Ehrenfeucht in the context of text algorithms in 1993. In 2004, S. Marcus extended the concept of coverability to (one-sided) infinite sequences. In this presentation, we will define the notion of coverable bi-infinite shifts.

In general, coverability of subshifts is not topologically invariant. Nevertheless, we show that a special type of coverability of substitutive shifts is invariant under topological conjugacy. To better understand coverability of bi-infinite shifts, we aim to identify properties of substitutions that ensure coverability or non-coverability of its associated shifts.

This is joint work with Manuel Joseph Loquias and Eden Delight Miro.

15:30 Ibai Aedo On long arithmetic progressions in binary Morse-like words


In this talk, I will present a joint work with Uwe Grimm, Yasushi Nagai and Petra Staynova based on a recent preprint: arXiv:2101.02056. Regarding the Prouhet-Thue-Morse word as a two-colouring of the positive integers, we look for long monochromatic arithmetic progressions occurring in the sequence.

The size of the longest arithmetic progression of difference $d=2^n-1$ was previously established by O. Parshina. Using a different approach, mainly based on exploiting the substitution structure of the Prouhet-Thue-Morse word, we will show how we can re-establish this result and find another series of long arithmetic progressions of difference d=2^n+1. Then, we will comment on a generalisation of these results for a special class of bijective binary words, and we will finish with some more general results and some open questions.

16:00 Francesco Dolce On morphisms preserving palindromic richness


A finite word is said to be rich if it has maximal number of palindromic factors (this is known to be the length of the word plus one). This definition can be naturally extended to infinite words.Sturmian words and Rote complementary symmetric sequences form two classes of binary rich words, while strict episturmian words and words coding symmetric interval exchange transformations give us other examples on larger alphabets. In this talk we study homomorphisms of the free monoid which allow to construct new rich words from already known rich words. In particular, we focus on two types of morphisms: Arnoux-Rauzy morphisms and morphisms from Class $P_{ret}$. These morphisms contain Sturmian morphisms as a subclass. We show that Arnoux-Rauzy morphisms preserve the set of all rich words. We also characterize $P_{ret}$ morphisms which preserve richness on binary alphabet. This is a joint work with Edita Pelantová.

16:30 Jeffrey Shallit Robbins and Ardila meet Berstel


In this short talk I show how to obtain a result of Robbins and (later) Ardila on partitions of integers in Fibonacci numbers, and much more, using a 2001 transducer created by Jean Berstel. The “fun” part is that once you have Berstel's transducer, the rest follows by purely computational means.

17:00 Anna E. Frid The semigroup of trimmed morphisms


We start a study of possible orders of morphic images of words. In the binary case, it is known that every morphism is either order-preserving or order-reversing. For larger alphabets, the situation can be much more complicated.

  • shorttalksmarch2021.txt
  • Last modified: 2021/03/22 22:46
  • by anna.frid