We prove a density version of the Carlson–Simpson Theorem. Specifically we show the following. For every integer $k\ge 2$ and every set $A$ of words over $k$ satisfying $\lim {\sup }_{n\to \infty }|A\cap {\left[k\right]}^n|/k^n>0$ there exist a word $c$ over $k$ and a sequence $\left(w_n\right)$ of left variable words over $k$ such that the set $c\cup \{c^{}{w}_0{\left(a_0\right)}^{}..{.}^{}{w}_n\left(a_n\right):n\in \mathbb{N}\text{and}{a}_0,...,a_n\in \left[k\right]\}$ is contained in $A$. While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

We investigate the extremal function $f(u,n)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v=a_1{a}_2...a_m$ of integers such that 1) $1\le a_i\le n$, 2) $a_i=a_j,i\ne j$ implies $|i-j|\ge k$ and 3) $v$ contains no subsequence of the type $u$. We prove that $f(u,n)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that $$f(u,n)=O\left(n{2}^{O\left(\alpha {\left(n\right)}^{\left|u\right|-4}\right)}\right).$$ Here $\left|u\right|$ is the length of $u$ and $\alpha \left(n\right)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

We generalize to all interval exchanges the induction algorithm defined by Ferenczi and Zamboni for a particular class. Each interval exchange corresponds to an infinite path in a graph whose vertices are certain unions of trees we call castle forests. We use it to describe those words obtained by coding trajectories and give an explicit representation of the system by Rokhlin towers. As an application, we build the first known example of a weakly mixing interval exchange outside the hyperelliptic...

We present an algorithm which produces, in some cases, infinite words avoiding both large fractional repetitions and a given set of finite words. We use this method to show that all the ternary patterns whose avoidability index was left open in Cassaigne's thesis are 2-avoidable. We also prove that there exist exponentially many ${\frac{7}{4}}^{+}$-free ternary words and ${\frac{7}{5}}^{+}$-free 4-ary words. Finally we give small morphisms for binary words containing only the squares 2, 12 and (01)² and for binary words avoiding...

We present an algorithm which for any aperiodic and primitive substitution outputs a finite representation of each special word in the shift space associated to that substitution, and determines when such representations are equivalent under orbit and shift tail equivalence. The algorithm has been implemented and applied in the study of certain new invariants for flow equivalence of substitutional dynamical systems.

We first prove an extremal property of the infinite Fibonacci* word f: the family of the palindromic prefixes {hn | n ≥ 6} of f is not only a circular code but “almost” a comma-free one (see Prop. 12 in Sect. 4). We also extend to a more general situation the notion of a necklace introduced for the study of trinucleotides codes on the genetic alphabet, and we present a hierarchy relating two important classes of codes, the comma-free codes and the circular ones.

We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above...

Let $w$ be an equality word of two binary non-periodic morphisms $g,h:{\{a,b\}}^{*}\to {\Delta }^{*}$ with unique overflows. It is known that if $w$ contains at least 25 occurrences of each of the letters $a$ and $b$, then it has to have one of the following special forms: up to the exchange of the letters $a$ and $b$ either $w={\left(ab\right)}^{i}a$, or $w=a^i{b}^j$ with $gcd(i,j)=1$. We will generalize the result, justify this bound and prove that it can be lowered to nine occurrences of each of the letters $a$ and $b$.

Among Sturmian words, some of them are morphic, i.e. fixed point of a non-identical morphism on words. Berstel and Séébold (1993) have shown that if a characteristic Sturmian word is morphic, then it can be extended by the left with one or two letters in such a way that it remains morphic and Sturmian. Yasutomi (1997) has proved that these were the sole possible additions and that, if we cut the first letters of such a word, it didn't remain morphic. In this paper, we give an elementary and combinatorial...

We propose a variation of Wythoff’s game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.

We propose a variation of Wythoff's game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.

We prove a long standing conjecture of Duval in the special case of sturmian words.