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.
last update: 27.9.2007, webmaster: Petr Ambrož