Booth Id:
MATH002I
Category:
Year:
2015
Finalist Names:
Zolotov, Boris
Abstract:
My work is devoted to generating series of infinite words without repetitions.
At the beginning of XX century the problem on constructing infinite non-repeating words was raised by a mathematician Axel Thue. In 1906, he wrote an article where he proved that such words exist, and provided some examples.
The theory of non-repeating words has found its applications in many branches of science — in the group theory, genetics, game theory (chess), etc. Many articles and monographies on this subject have been published.
A squarefree (cubefree) word is a word without factors of the form XX (XXX, respectively). An overlap-free (weakly squarefree) word is a word without factors of the form aXaXa (aXXa, respectively).
A morphism preserves the absence of patterns of some form if the image of any word without patterns of this form does not contain patterns of this form. A Thue morphism is a morphism that preserves overlap- and cubefreeness, and also generates an infinite word.
So, the main results of this work are:
1. The open problem on existence of uniform weakly squarefree Thue morphisms over the ternary alphabet was solved.
2. It was proved that there are no such morphisms with a rank lower than 5.
3. Also, all the squarefree morphisms of the optimal rank were found and described.
4. It was proved that there exist morphisms over ternary alphabet that have all four non-repeating properties. Also, it was proved that the optimal rank for these morphisms is equal to 13.
5. Lastly, what was found was the maximal length of squarefree words without some squarefree factors of length 2 or 3.
As a conclusion we can say that new sets of non-repeating words and morphisms were constructed. These results can be applied in semigroup theory, for example.