Combinatorical and Algebraic Structures Seminar

Session details

Date: 2.4.2019
Speaker: Edita Pelantová, FJFI, České vysoké učení technické v Praze
Title: Antipalindromy v nekonečných binárních řetězcích
Abstract: (spoluautoři: P. Ambrož, Z. Masáková)
Nekonecne retezece, v nichz lze najit libovolne dlouhe kusy, ktere se ctou zleva doprava stejne jako pozpatku, se nazyvaji palindromicke. Prikladem takoveho retezce je Fibonacciho retezec $F$, ktery vznikne opakovanim prepisovaciho pravidla: ``$0$ nahrad $01$ a $1$ nahrad $0$'' $$ 0\mapsto 01 \mapsto 010 \mapsto 01001 \mapsto \cdots \mapsto 010010100100101001010 0100101001001 \cdots $$ Napr. palindrom 001001010010100100 delky 18 zacina na 8. pozici retezce $F$. Znama HKS domnenka definuje tridu prepisovacich pravidel -- tzv. Class P -- a zhruba receno rika, ze jenom prepisovaci pravidla z teto tridy generuji nekonecne palindromicke retezce. Tato domnenka byla dokazana zatim pouze pro binarni retezce Bo Tanem v roce 2007. Na binarni abecede je antipalindrom definovan jako slovo, ktere je pri cteni pozpatku stejne jako zepredu, pokud pri zpatecnem cteni vymenujeme 0 a 1. Antipalindromem je napr. slovo 011001. Analogicky se nekonecny retezec nazyva antipalindromicky, pokud obsahuje antipalindromy libovolne delky. Prikladem antipalindromickeho retezce je Thue-Morseuv retezec, ktery vznikne opakovanim prepisovaciho pravidla: ``$0$ nahrad $01$ a $1$ nahrad $10$'' $$ 0\mapsto 01 \mapsto 0110 \mapsto 0110 1001 \mapsto \cdots \mapsto 0110 1001 1001 0110 1001011001101001 \cdots $$ V nasem prispevku popiseme dve tridy prepisovacich pravidel A1 a A2, ktere generuji antipalindromicke retezce. Vyslovime domnenku, ze kazdy antipalindromicky retezec lze takto ziskat. Domnenku podporime dukazem vety: Pokud nekonecny retezec generovany prepisovacim pravidlem je soucasne palindromicky a antipalindromicky, pak je generovany pravidlem z pruniku trid P a A1 nebo pruniku trid P a A2.

Return to index.