Combinatorical and Algebraic Structures Seminar

Session details

Date: 17.12.2013
Speaker: Ondřej Turek, BLTP, Joint Institute for Nuclear Research
Title: Abelovská komplexita Tribonacciho slova
Abstract: Tribonacciho slovo $\mathbf{t}$ nad abecedou $\mathcal{A}=\{0,1,2\}$ je definováno jako pevný bod substituce $\varphi: \; 0 \mapsto 01, \; 1 \mapsto 02, \; 2 \mapsto 0$, tj. $$\mathbf{t}=\lim_{k\to\infty}\varphi^k(0)=010201001020101020100102\cdots$$ Libovolné jeho dva faktory $v,w$ o stejném počtu písmen se nazývají abelovsky ekvivalentní, $v\sim_{\mathrm{ab}}w$, jestliže lze převést jeden na druhý permutací znaků. Relace $v\sim_{\mathrm{ab}}w$ rozděluje množinu faktorů slova $\mathbf{t}$ na třídy ekvivalence. Abelovská komplexita Tribonacciho slova je funkce $\rho^{\mathrm{ab}}_\mathbf{t}$, vyjadřující počet tříd ekvivalence příslušných délce $n\in\mathbb{N}$. Richomme, Saari a Zamboni odvodili, že funkce $\rho^{\mathrm{ab}}_\mathbf{t}$ splňuje pro každé $n$ nerovnosti $3\leq\rho^{\mathrm{ab}}_\mathbf{t}(n)\leq7$. Na semináři ukážeme, jak pro libovolné $n\in\mathbb{N}$ přesně určit hodnotu $\rho^{\mathrm{ab}}_\mathbf{t}(n)$, a to v $\mathcal{O}(\log n)$ krocích.

Return to index.