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