Combinatorical and Algebraic Structures Seminar

Session details

Date: 26.3.2013
Speaker: Edita Pelantová, FJFI, České vysoké učení technické v Praze
Title: Zobecněné palindromické uzávěry
Abstract: (spoluautoři: T. Jajcayová a Š. Starosta)
Palindromický uzávěr slova $w$ je nejkratší palindrom, který má slovo $w$ za svůj prefix. Např. Tribonacciho slovo $u=0102010010201010200\ldots$, které je definováno jako pevný bod substituce $h(0) = 01, h(1) = 02, h(2) = 0$, lze zkonstruovat pomocí řídící periodické posloupnosti $\Delta = (012)^\omega$ opakováním operace palindromický uzávěr za postupného přidávání písmen z $\Delta$. Palindrom je pevný bod zrcadlení, tedy operace $R$, která slovu $w=w_1w_2 \ldots w_n$ přiřadí slovo $R(w)=w_nw_{n-1} \ldots w_1$. Nahradíme-li zrcadlení $R$ jiným involutivním antimorfizmem $\theta$, můžeme mluvit o $\theta$-palindromech a $\theta$-palindromických uzávěrech. V přednášce nejdříve shrneme známé výsledky o nekonečných slovech, která vznikají pomocí palindromických uzávěrů při použití jednoho pevného antimorfizmu. Pak nahradíme řídící posloupnost dvojicí posloupností, a to posloupností písmen $\Delta = (\delta_n)$ a posloupností antimorfizmů $\Theta=(\theta_n)$ a studujeme nekonečná slova, která vzniknou pomocí $\theta$-palindromických uzávěrů, přičemž za $\theta$ bereme postupně prvky $\Theta$. Ukážeme, že Thue-Morseovo slovo i jeho zobecnění na vícepísmennou abecedu lze získat zmíněnou konstrukcí. Stejné tvrzení platí i pro standardní Roteovy slova, jak nedávno ukázali Blondin-Masé et al. Jazyk všech slov vzniklých pomocí zobecněných palindromických uzávěrů je ivariantní na grupu $G$ generovanou antimorfizmy, které se v posloupnosti $\Theta$ vyskytují nekonečně krát. Mezi těmito slovy proto nacházíme dosud chybějící příklady $G$-bohatých slov.

Return to index.