One World Combinatorics on Words Seminar

The seminar takes place biweekly on Mondays at 15:00 CET. In summer, it means 6:00 in California, 9:00 in New-York or Waterloo, 14:00 in London, 15:00 in Paris, 16:00 in Moscow and 22:00 in Tokyo. In winter, some of these numbers change. Please check in advance the time in your time zone.

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.

Mar 27 2023: Štěpán Starosta On a faithful representation of Sturmian morphisms

The set of morphisms mapping any Sturmian sequence to a Sturmian sequence forms together with composition the so-called monoid of Sturm. For this monoid, we define a faithful representation by $(3\times 3)$-matrices with integer entries. We find three convex cones in $\mathbb{R}^3$ and show that a matrix $R \in Sl(\mathbb{Z},3)$ is a matrix representing a Sturmian morphism if the three cones are invariant under multiplication by $R$ or $R^{-1}$. This property offers a new tool to study Sturmian sequences. We provide alternative proofs of four known results on Sturmian sequences fixed by a primitive morphism and a new result concerning the square root of a Sturmian sequence.

April 3 2023: Jeffrey O. Shallit New Results in Additive Number Theory via Combinatorics on Words

Additive number theory is the study of the additive properties of integers. Surprisingly, we can use techniques from combinatorics on words to prove results in this area. In this talk I will discuss the number of representations of an integer N as a sum of elements from some famous sets, such as the evil numbers, the odious numbers, the Rudin-Shapiro numbers, Wythoff sequences, etc.

April 17 2023: Bastián Espinoza An $S$-adic characterization of linear-growth complexity subshifts

In the context of symbolic dynamics, the class of “linear-growth complexity subshifts” is of particular relevance as it occurs in a variety of areas, such as geometric dynamical systems, language theory, number theory, and numeration systems, among others. During the intensive study carried out on this subject since the beginning of the 90s, it was proposed that a hierarchical decomposition based on $S$-adic sequences that characterizes linear-growth complexity subshifts would be useful to understand this class. The problem of finding such a characterization was given the name “$S$-adic conjecture” and inspired several influential results in symbolic dynamics. In this talk, I will present an $S$-adic characterization of this class as well as some of its applications, giving in particular a solution to this conjecture.

May 8 2023: |Mélodie Lapointe

May 22 2023: Matthieu Rosenfeld

Mar 6 2023: Léo Poirier and Wolfgang Steiner Factor-balanced $S$-adic languages

slides

A set of words, also called a language, is letter-balanced if the number of occurrences of each letter only depends on the length of the word, up to a constant. Similarly, a language is factor-balanced if the difference of the number of occurrences of any given factor in words of the same length is bounded. The most prominent example of a letter-balanced but not factor-balanced language is given by the Thue-Morse sequence. We establish connections between the two notions, in particular for languages given by substitutions and, more generally, by sequences of substitutions. We show that the two notions essentially coincide when the sequence of substitutions is proper. For the example of Thue-Morse-Sturmian languages, we give a full characterisation of factor-balancedness.

Feb 27 2023: Aline Parreau and Eric Duchêne Taking and merging games as rewrite games (joint work with V. Marsault and M. Rigo)

slides

In this talk, we present some of the links between combinatorial games and language theory. A combinatorial game is a 2-player game with no chance and with perfect information. Amongst them, the family of heap games such as the game of Nim, subtraction or octal games belong to the the most studied ones. Generally, the analysis of such games consist in determining which player has a winning strategy. We will first see how this question is investigated in the case of heap games.

In a second part of the talk, we will present a generalization of heap games as rewrite games on words. This model was introduced by Waldmann in 2002. Given a finite alphabet and a set of rewriting rules on it, starting from a finite word w, each player alternately applies a rule on w. The first player unable to apply a rule loses the game. In this context, the main question is now about the class of the language formed by the losing and winning positions of the game. For example, for octal games that are solved in polynomial time, the losing positions form a rational language. By using the model of rewrite games, we will investigate here a new family of heap games that consist in merging heaps of tokens, and consider some of the different classes of languages that may emerge according to the rules of the game.

Feb 6 2023: Matthew Konefal Examining the Class of Formal Languages which are Expressible via Word Equations

slides

A word equation can be said to express a formal language via each variable occurring in it. The class $WE$ of formal languages which can be expressed in this way is not well understood. I will discuss a number of necessary and sufficient conditions for a formal language $L$ to belong to $WE$. I will give particular focus to the case in which $L$ is regular, and to the case in which $L$ is a submonoid.

Jan 23 2023: Lubomíra Dvořáková Essential difference between the repetitive thereshold and asymptotic repetitive threshold of balanced sequences

slides

At first, we will summarize both the history and the state of the art of the critical exponent and the asymptotic critical exponent of balanced sequences. Second, we will colour the Fibonacci sequence by suitable constant gap sequences to provide an upper bound on the asymptotic repetitive threshold of $d$-ary balanced sequences. The bound is attained for $d$ equal to $2$, $4$ and $8$ and we conjecture that it happens for infinitely many even $d$'s. Finally, we will reveal an essential difference in behavior of the repetitive threshold and the asymptotic repetitive threshold of balanced sequences: The repetitive threshold of $d$-ary balanced sequences is known to be at least $1+1/(d-2)$ for each $d$ larger than two. In contrast, our bound implies that the asymptotic repetitive threshold of $d$-ary balanced sequences is at most $1+\phi^3/2^{d-3}$ for each $d$ larger than one, where $\phi$ is the golden mean.

Joint work with Edita Pelantová.

Jan 9: Pamela Fleischmann $m$-Nearly $k$-Universal Words - Investigating Simon Congruence

Determining the index of the Simon congruence is a long outstanding open problem. Two words $u$ and $v$ are called Simon congruent if they have the same set of scattered factors, which are parts of the word in the correct order but not necessarily consecutive, e.g., oath is a scattered factor of logarithm. Following the idea of scattered factor $k$-universality, we investigate $m$-nearly $k$-universality, i.e., words where $m$ scattered factors of length $k$ are absent, w.r.t. Simon congruence. We present a full characterisation as well as the index of the congruence for $m = 1$, $2$, and $3$. Moreover, we present a characterisation of the universality of repetitions.

slides