Combinatorical and Algebraic Structures Seminar

Session details

Date: 22.2.2011
Speaker: Edita Pelantová a Štěpán Starosta, FJFI, České vysoké učení technické v Praze
Title: Slova bez překryvu a bohatost na palindromy
Abstract: Pro nekonečná slova s jazykem uzavřeným na zrcadlení platí nerovnost \begin{equation}\label{1} \mathcal{C}(n+1)-\mathcal{C}(n) +2 \geq \mathcal{P}(n+1)+\mathcal{P}(n) \quad \hbox{pro každé} \ n\in \mathbb{N}, \end{equation} kde $\mathcal{C}(n)$ je faktorová a $\mathcal{P}(n)$ palindromická komplexita slova. O nekonečném slově řekneme, že je bohaté na palindromy, pokud v (\ref{1}) platí rovnost pro každé $n\in \mathbb{N}$. Pokud rovnost platí od jistého $n$ počínaje, nazývame slovo téměř bohaté na palindromy. Ukážeme, že nekonečná slova, která jsou téměř bohatá na palindromy, obsahují nekonečně mnoho překrývajících se faktorů. Stejné tvrzení zůstane v platnosti, když zrcadlení nahradíme libovolným involutivním antimorfizmem $\Theta$ a palindromickou komplexitu slova nahradíme $\Theta$-palindromickou komplexitou $\mathcal{P}_\Theta(n)$. Thue-Morseovo slovo TM -- slavný první příklad nekonečného slova bez překryvů -- tedy nemůže být téměř bohaté na $\Theta$-palindromy pro žádné $\Theta$. Pro slova, jejichž jazyk je uzavřený na dva involutivní antimorphismy $\Theta_1$ a $\Theta_2$, dokážeme, že pro každé $ n\in \mathbb{N}$ platí silnější nerovnost \begin{equation}\label{2} \mathcal{C}(n+1)-\mathcal{C}(n) +4 \geq \mathcal{P}_{\Theta_1}(n+1)+\mathcal{P}_{\Theta_1}(n) + \mathcal{P}_{\Theta_2}(n+1)+\mathcal{P}_{\Theta_2}(n) - \Pi(n)- \Pi({n+1}), \end{equation} kde $\Pi(n)$ značí počet faktorů délky $n$, které jsou současně $\Theta_1$- a $\Theta_2$-palindromy. Slovo TM má jazyk uzavřený jak na zrcadlení, tak na další involutivní antimorfizmus. Ukážeme, že pro toto slovo platí v (\ref{2}) rovnost pro každé $n$. Slovo TM je tedy bohaté na $\Theta_1$- a $\Theta_2$-palindromy v tomto novém smyslu.

Return to index.