This 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 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

Mélodie Andrieu A Rauzy fractal unbounded in all directions of the plane

Until 2001 it was believed that, as for Sturmian words, the imbalance of Arnoux-Rauzy words was bounded - or at least finite. Cassaigne, Ferenczi and Zamboni disproved this conjecture by constructing an Arnoux-Rauzy word with infinite imbalance, i.e. a word whose broken line deviates regularly and further and further from its average direction. Today, we hardly know anything about the geometrical and topological properties of these unbalanced Rauzy fractals. The Oseledets theorem suggests that these fractals are contained in a strip of the plane: indeed, if the Lyapunov exponents of the matricial product associated with the word exist, one of these exponents at least is nonpositive since their sum equals zero. The study of the pairs of abelianized factors of Arnoux-Rauzy words disproves this belief.

Anna Frid The semigroup of trimmed morphisms

Štěpán Holub Formalization of Combinatorics on Words in Isabelle/HOL

We present an ongoing project of formalization of Combinatorics on Words in the proof assistant Isabelle/HOL.

Florin Manea Efficiently Testing Simon's Congruence full text

Simon's congruence $\sim_k$ is a relation on words defined by Imre Simon in the 1970s and intensely studied since then. This congruence was initially used in connection to piecewise testable languages, but also found many applications in, e.g., learning theory, databases theory, or linguistics. The $\sim_k$-relation is defined as follows: two words are $\sim_k$-congruent if they have the same set of subsequences of length at most $k$. A long standing open problem, stated already by Simon in his initial works on this topic, was to design an algorithm which computes, given two words $s$ and $t$, the largest $k$ for which $s\sim_k t$. We propose the first algorithm solving this problem in linear time $O(|s|+|t|)$ when the input words are over the integer alphabet $\{1,\ldots,|s|+|t|\}$ (or other alphabets which can be sorted in linear time). Our approach can be extended to an optimal algorithm in the case of general alphabets as well.

To achieve these results, we introduce a novel data-structure, called Simon-Tree, which allows us to construct a natural representation of the equivalence classes induced by $\sim_k$ on the set of suffixes of a word, for all $k\geq 1$. We show that such a tree can be constructed for an input word in linear time. Then, when working with two words $s$ and $t$, we compute their respective Simon-Trees and efficiently build a correspondence between the nodes of these trees. This correspondence, which can also be constructed in linear time $O(|s|+|t|)$, allows us to retrieve the largest $k$ for which $s\sim_k t$.

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.