Combinatorical and Algebraic Structures Seminar

Session details

Date: 2.11.2010
Speaker: Karel Klouda, FIT, České vysoké učení technické v Praze
Title: S-adic conjecture
Abstract: We give a survey of results related to the $S$-adic conjecture. A (right) infinite word $\mathbf{w}$ is called $S$-adic if there exist a finite set of morphisms $S = \{\sigma_0, \sigma_1, \ldots, \sigma_m\}$, a sequence $(\sigma_{i_j})_{j \geq 1}$ with $\sigma_{i_j} \in S$ and a letter $a$ such that \[ \mathbf{w} = \lim_{n \to \infty} \sigma_{i_0}\sigma_{i_1}\cdots\sigma_{i_n}(aaa\cdots)\,. \] It is easy to prove that any word over a finite alphabet is an $S$-adic word for some set $S$. However, it is believed that there exists a condition $C$ on $S$ so that ``a word $\mathbf{w}$ has sublinear factor complexity if and only if $\mathbf{w}$ is $S$-adic for a set $S$ satisfying the condition $C$''. The $S$-adic conjecture claims that some (reasonable) condition $C$ exists.
Slides: 20101102.pdf

Return to index.