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.

Upcoming talks

26 April 2021: Luca Zamboni Singular words

The extremal solutions to certain problems in the theory of finite continued fractions are characterised by a special combinatorial property which we call the singular property. This property may be interpreted in the framework of finite words, cyclic words, and one and two-sided infinite words over arbitrary ordered alphabets. Each linear (resp. cyclic) word w is Abelian equivalent to a singular linear (resp. cyclic) word w’ which is in general unique up to reversal. We develop an algorithm for generating all singular words having a prescribed Parikh vector which is based in part on a non-commutative variant of the usual Euclidean algorithm. This allows us to answer a question of G. Ramharter from 1983 on the extremal values of the regular and semi-regular cyclic continuants introduced by Motzkin and Straus in the 1950’s. We also confirm a conjecture of Ramharter in certain instances and exhibit counter examples in other cases. As for infinite words, the singular property in the context of bi-infinite binary words coincides with the Markoff property which was shown by C. Reutenauer to be equivalent to the balance property. We generalise this to higher alphabets by showing that the singular property is the fundamental property which characterises the language structure of codings of symmetric k-interval exchange transformations. This is based on a collaboration with Alessandro De Luca and Marcia Edson initiated during the first Covid lockdown of 2020.

3 May 2021: Gwenaël Richomme On sets of indefinitely desubstitutable words

The stable set associated to a given set $S$ of nonerasing endomorphisms or substitutions is the set of all right infinite words that can be indefinitely desubstituted over $S$. This notion generalizes the notion of sets of fixed points of morphisms. It is linked to $S$-adicity and to property preserving morphisms. Two main questions are considered. Which known sets of infinite words are stable sets? Which ones are stable sets of a finite set of substitutions? While bringing answers to the previous questions, some new way of characterizing several well-known sets of words such as the set of binary balanced words or the set of episturmian words are presented. A characterization of the set of nonerasing endomorphisms that preserve episturmian words is also provided.

10 May 2021: Kevin Buzzard

17 May 2021: Jeffrey Shallit The Walnut Tutorial: Using A Tool for Doing Combinatorics on Words

Walnut is free open-source software, written by Hamoon Mousavi, that can rigorously prove or disprove claims about automatic sequences (broadly understood), such as the Thue-Morse sequence, the Fibonacci infinite word, and others. It can also be used to create explicit formulas for various aspects of such sequences, such as subword complexity, palindrome complexity, and so forth.

In this talk I won't discuss how it works. Instead I'll give a tutorial, surveying the kinds of things you can and can't do with it. We'll “get our hands dirty” and solve problems in real time.

At the end, if there's time, I'll solicit problems about such sequences from the audience and try to solve them with Walnut. Come prepared with some conjecture you haven't been able to prove yet!

The tutorial will last about 90 minutes.

31 May 2021: Etienne Moutot

7 June 2021: Pascal Ochem

14 June 2021: Golnaz Badkobeh

21 June 2021: Day of short talks

As usual, the event will consist of short talks in 25-minute slots. You are welcome to apply by writing a message to Anna Frid. Speakers:

  • Jarosław Duda Generalized Fibonacci coding problem using Maximal Entropy Random Walk and Asymmetric Numeral Systems
  • Palak Pandoh Counting scattered palindromes in a finite word
  • Jarkko Peltomäki Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents

28 June 2021: Florin Manea

12 July 2021: Štěpán Holub

26 July 2021: Jason Bell

Past talks 2021

12 April 2021: Valérie Goyheneche Eigenvalues and constant arithmetical progressions for substitutive sequences

slides

The main subject of this talk is to answer the following decidability question : does a substitutive sequence $x$ admit a constant arithmetical progression $ (x_{k+np})_n $?

Our method mainly relies on the link between constant arithmetical subsequences and (dynamical) eigenvalues of the underlying dynamical system. We will explain a method to compute the set of (additive) eigenvalues associated to such systems. We can then deduce, given an integer $p$, if the sequence $x$ contains a constant arithmetical progression with period $p$. At the end of the talk, we will focus on the case of primitive constant-length substitutions, for which the set of such periods can be described by an automaton.

29 March 2021: Jacques Sakarovitch, RIF, CNRS / Univ. de Paris and Télécom Paris, IPP From Fibonacci to golden mean representations

The video will not be distributed, but we hope to get the slides later.

Every positive integer can be written as a sum of Fibonacci numbers; this yields a Fibonacci representation of the integer. A positive integer can also be written as a (finite) sum of (positive and negative) powers of the golden mean; this yields a golden mean representation of the integer, with the radix point roughly in the middle of the writing. It is the golden mean expansion when it contains no consecutive digits equal to 1.

We show that there exists a letter-to-letter finite two-tape automaton that maps the Fibonacci representation of any positive integer onto its golden mean expansion, provided the latter is folded around the radix point. As a corollary, the set of golden mean expansions of the positive integers is a linear context-free language.

These results are generalised to the more general case of integer representations in numeration systems built upon quadratic Pisot units.

Joint work with Christiane Frougny, published in 1999 in the Journal of Algebra and Computation. This talk is a follow-up to the one of October 15 by Michel Dekking, who kindly quoted this paper but deemed it hard to understand.

22 March 2021: Day of Short Talks

This second event also consisted of short talks in 25-minute slots.

  • 15:00 Jane D. Palacio Coverable bi-infinite substitution shifts
  • 15:30 Ibai Aedo On long arithmetic progressions in binary Morse-like words
  • 16:00 Francesco Dolce On morphisms preserving palindromic richness
  • 16:30 Jeffrey Shallit Robbins and Ardila meet Berstel
  • 17:00 Anna E. Frid The semigroup of trimmed morphisms

See the event page for the abstracts; slides and videos of talks.

15 March 2021: Szymon Stankiewicz Square-free reducts of words

slides

We discuss a joint work with Jarosław Grytczuk (https://arxiv.org/abs/2011.12822) about square-free reducts of words.

In any finite word one may delete the repeated block of a square, obtaining thereby a shorter word. By repeating this process, a square-free word is eventually reached, which we call a reduct of the original word.

We will show that for each positive integer $n$ there is a word over ternary alphabet which can be reduced to at least $n$ different words and also that there is a word over alphabet of size four which has exactly $n$ reducts. We will also show that there exists infinitely many ternary words having exponential many reducts in the length of these words.

For a fixed alphabet one can create a poset with nodes being words and $u > v$ iff word $u$ can be reduced to word $v$. We will describe some properties of those posets.

1 March 2021: Mickaël Postic Open and closed complexity functions of infinite words

slides

Closed words, also known as complete first returns, have been studied for a long time, and play an important role in symbolic dynamics. A word which is not closed is said to be open. In this talk based on a joint work with Olga Parshina, I will present a characterization of aperiodic words in terms of their open complexity function and closed complexity function, in the spirit of Morse and Hedlund's theorem. The preprint is available at https://arxiv.org/pdf/2005.06254.pdf

22 February 2021: Day of Short Talks

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 consisted of short talks in 25-minute slots. Speakers:

  • 15:30 Célia Cisternino Two applications of the composition of a $2$-tape automaton and a weighted automaton
  • 16:00 Lubka Dvořáková On balanced sequences with the minimal asymptotic critical exponent
  • 16:30 Štěpán Holub Formalization of Combinatorics on Words in Isabelle/HOL
  • 17:30 Mélodie Andrieu A Rauzy fractal unbounded in all directions of the plane

For the abstracts, slides and videos of the talks, see the event page.

15 February 2021: Petr Ambrož Morphisms generating antipalindromic words

slides

We introduce two classes of morphisms over the alphabet $A=\{0,1\}$ whose fixed points contain infinitely many antipalindromic factors. An antipalindrome is a finite word invariant under the action of the antimorphism $E:\{0,1\}^*\to\{0,1\}^*$, defined by $E(w_1\cdots w_n)=(1-w_n)\cdots(1-w_1)$. We conjecture that these two classes contain all morphisms (up to conjugation) which generate infinite words with infinitely many antipalindromes. This is an analogue to the famous HKS conjecture concerning infinite words containing infinitely many palindromes. We prove our conjecture for two special classes of morphisms, namely (i) uniform morphisms and (ii) morphisms with fixed points containing also infinitely many palindromes.

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

slides

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.

1 February 2021: Jean-Paul Allouche Hidden automatic sequences

slides

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.

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.

Archives 2020

The talks of 2020 are available here.

Lectures on combinatorics on words

Several starting lectures by Anna Frid are available here.

  • start.txt
  • Last modified: 2021/04/21 13:02
  • by anna.frid