Combinatorical and Algebraic Structures Seminar

Session details

Date: 23.2.2007
Speaker: Ľubomíra Balková, FJFI, České vysoké učení technické
Title: All about primitive substitutions
Abstract: Substitution is a~non-erasing morphism $\varphi :{\cal A}^{*} \rightarrow {\cal A}^{*}$ such that there exists $d \in {\cal A}$ satisfying $\varphi(d)=dw$ for some non-empty word $w \in \cal A^{*}$. If $\varphi(u)=u$, then $u$ is called a~fixed point of $\varphi$. A~substitution $\varphi$ over the alphabet $\cal A$ is called {\em primitive} if there exists $k \in \mathbb N$ such that for any $d \in \cal A$, the word $\varphi^{k}(d)$ contains all the letters of $\cal A$. The substitution matrix of a~primitive substitution is primitive, thus, we can make use of the Perron-Frobenius theorem to prove that any fixed point $u$ of a~primitive substitution is linearly recurrent and that frequencies of factors of $u$ exist. Moreover, we will introduce some interesting properties of linearly recurrent words, and, at the end of the lecture, we will focus on a~special class of primitive substitutions --- Pisot substitutions.

Return to index.