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.
last update: 27.9.2007, webmaster: Petr Ambrož