Combinatorical and Algebraic Structures Seminar

Session details

Date: 18.11.2008
Speaker: Dominik Macáš, FJFI, České vysoké učení technické
Title: Sturmovská slova a výskyt palindromů v jejich jazyku
Abstract: Připomeneme definici tzv. sturmovského slova, tedy slova, pro které platí vztah $\#(\mathcal{L}_n(u))=n+1$. Uvedeme jeho základní kombinatorické vlastnosti. Už z definice plyne, že pro každé $n$ přirozené existuje pouze jeden pravý speciál délky $n$. Dále platí, že každý faktor sturmovského slova se v něm vyskytuje nekonečně mnohokrát, včetně svého zrcadlového obrazu. Navíc, každé sturmovské slovo je 1-balancované. Vyslovíme, a pomocí těchto základních poznatků i dokážeme, že sturmovská slova je možno charakterizovat také pomocí počtu palindromických faktorů dané délky. Platí věta, že slovo je sturmovské tehdy a jen tehdy, je-li počet palindromických faktorů délky $n$ roven dvěma pro $n$ liché a jedné pro $n$ sudé.

Return to index.