Palindromy v nekoneˇcn´ych slovech modeluj´ıc´ıch kvazikrystaly ˇ Lubom´ ıra Balkov´a ˇ CVUT, Fakulta jadern´a a fyzik´alnˇe inˇzen´yrsk´a, Katedra matematiky
Palindromy zn´ am´ e nezn´ am´ e Palindromick´a slova a palindromick´e vˇety, tedy slova a vˇety, kter´e z˚ ust´avaj´ı stejn´e, ˇ aˇt je ˇcteme odpˇredu ˇci odzadu, jsou obl´ıbenou hr´atkou. Ceˇstina n´as m˚ uˇze pobavit palindromick´ymi vˇetami jako: Kobyla m´ a mal´y bok. Jelenovi pivo nelej. Nevypusˇt supy ven. Nejdelˇs´ım palindromick´ym slovem nalezen´ym v Oxfordsk´em slovn´ıku je tattarrattat, coˇz je slovo vznikl´e ve fantazii Jamese Joyce a pouˇzit´e v rom´anu Odysseus, kter´e znamen´a “klepat na dveˇre”. V Guinnessovˇe knize rekord˚ u je uvedeno slovo detartrated, minul´y ˇcas slovesa detartrate, chemiky vymyˇseln´y term´ın, kter´y znamen´a odstranit v´ınan (skupina organick´ych l´atek). Ve slovn´ıc´ıch je ˇcasto uv´adˇen´y rotavator, obchodn´ı znaˇcka zemˇedˇelsk´eho stroje. Malayalam, indi´ansk´y jazyk, je palindromick´e slovo stejn´e d´elky. Zd´a se, ˇze nejdelˇs´ı v bˇeˇzn´e mluvˇe uˇz´ıvan´y palindrom je finsk´e slovo saippuakauppias, kter´e oznaˇcuje prodavaˇce m´ydla. V roce 1991 sestavil Gordon Dow palindromickou vˇetu obsahuj´ıc´ı 306 slov s titulem Dog Sees Ada. Tento palindrom si zaslouˇz´ı pozornost, protoˇze obsahuje jen m´alo ‘umˇel´ych’ slov. Ovˇsem palindromy se objevuj´ı i v seri´ozn´ıch discipl´ın´ach. Ve vˇetˇsinˇe genom˚ u (soubory gen˚ u obsaˇzen´e v chromoz´omech bunˇeˇcn´eho j´adra organism˚ u) se objevuj´ı palindromick´e motivy. Pod palindromem rozumˇej´ı biologov´e ovˇsem trochu odliˇsn´y pojem. DNA je tvoˇrena dvˇema vl´akny nukleotid˚ u a tyto b´aze jsou vz´ajemnˇe komplement´arn´ı, tj. vˇzdy se p´aruj´ı stejn´ym zp˚ usobem (adenin s tyminem a cytosin s guaninem). Posloupnost nukleotid˚ u ve vl´aknu DNA se pak naz´yv´a palindromem, pokud je rovna sv´e komplement´arn´ı posloupnosti ˇcten´e pozp´atku. Napˇr´ıklad posloupnost ACCTAGGT je palindromem, protoˇze pˇreˇctemeli jej´ı komplement TGGATCCA pozp´atku, dostaneme p˚ uvodn´ı posloupnost. Motivy formovan´e ˇrazen´ım nukleotid˚ u specifikuj´ı, jak´e b´ılkoviny maj´ı b´yt buˇ nkou produkov´any. Ned´avn´e v´yzkumy uk´azaly, ˇze mnoho b´az´ı chromoz´omu Y je uspoˇr´ad´ano palindromicky. Toto uspoˇr´ad´an´ı umoˇzn ˇ uje totiˇz chromoz´omu Y, dojde-li k jeho poˇskozen´ı, jednoduch´y samoopravn´y proces pomoc´ı pˇrekop´ırov´an´ı genetick´e informace sv´e ‘zdrav´e’ poloviny. V tomto ˇcl´anku se zamˇeˇr´ıme na jin´e odvˇetv´ı, kde se palindromy intenzivnˇe studuj´ı, a t´ım je teorie kvazikrystal˚ u. Objev kvazikrystal˚ u v roce 1982 [6] zp˚ usobil poprask. Kvazikrystaly jsou materi´aly s ostr´ymi body na difrakˇcn´ım obr´azku, ale z´aroveˇ n s nekrystalografick´ymi symetriemi. Tyto materi´aly mus´ı tedy b´yt uspoˇr´ad´any na dlouhou vzd´alenost, toto uspoˇr´ad´an´ı ovˇsem nen´ı periodick´e. Aˇz do doby objevu kvazikrystal˚ u se vˇeˇrilo, ˇze pravidelnost ve struktuˇre l´atek je synomem periodicity. K modelov´an´ı jednorozmˇern´ych kvazikrystal˚ u slouˇz´ı nˇekter´a nekoneˇcn´a neperiodick´a slova. Zkoum´an´ım jejich kombinatorick´ych a algebraick´ych vlastnost´ı
tak nepˇr´ımo studujeme fyzik´aln´ı vlastnosti kvazikrystal˚ u. Faktorov´ a komplexita odpov´ıd´a poˇctu lok´aln´ıch konfigurac´ı atom˚ u v materi´alu. Palindromick´ a komplexita popisuje lok´aln´ı symetrie materi´alu. My se zamˇeˇr´ıme na zkoum´an´ı palindrom˚ u jist´e skupiny nekoneˇcn´ych slov, kter´a jsou vhodn´ym modelem kvazikrystal˚ u.
Znaˇ cen´ı Abeceda A je koneˇcn´a mnoˇzina symbol˚ u zvan´ych p´ısmena. Zˇretˇezen´ım p´ısmen ∗ z´ısk´ame slovo. A je mnoˇzina vˇsech koneˇcn´ych slov nad abecedou A. Pokraˇcujemeli v ˇretˇezen´ı p´ısmen bez omezen´ı, z´ısk´ame doprava nekoneˇcn´e slovo u = u0 u1 u2 .... Analogicky z´ısk´ame doleva nekoneˇcn´e slovo. Faktor (podslovo) slova u je kaˇzd´e slovo (koneˇcn´e ˇci nekoneˇcn´e), kter´e se v u vyskytuje. P´ısmeno d ∈ A je lev´ym prodlouˇzen´ım faktoru v, pokud dv je faktor u. Slovo v je lev´y speci´ aln´ı faktor, pokud v m´a v´ıce lev´ych prodlouˇzen´ı. Slovo v je pˇredpona u, pokud u = vw pro nˇejak´y faktor w slova u. Jazyk L(u) je mnoˇzina vˇsech faktor˚ u slova u. Symbolem Ln (u) znaˇc´ıme mnoˇzinu vˇsech faktor˚ u d´elky n slova u. Symbolem ε znaˇc´ıme pr´azdn´e slovo. Substituce ϕ je homomorfismus : A∗ → A∗ takov´y, ˇze existuje d ∈ A splˇ nuj´ıc´ı ∗ ϕ(d) = dw pro nˇejak´e nepr´azdn´e slovo w ∈ A a ϕ(d) 6= ε pro kaˇzd´e d ∈ A. Substituce m˚ uˇze b´yt definov´ana pro doprava nekoneˇcn´e slovo u = u0 u1 u2 . . . pˇredpisem: ϕ(u) := ϕ(u0)ϕ(u1 )ϕ(u2 ) . . . Poznamenejme, ˇze kaˇzd´a substituce m´a pevn´y bod, tj. existuje nekoneˇcn´e slovo u takov´e, ˇze ϕ(u) = u. Substituce ϕ se naz´yv´a primitivn´ı, pokud existuje k ∈ N takov´e, ˇze pro kaˇzdou dvojici p´ısmen c, d ∈ A se p´ısmeno c vyskytuje ve slovˇe ϕk (d). Stejnomˇernˇe rekurentn´ı je takov´e nekoneˇcn´e slovo u, kter´e m´a n´asleduj´ıc´ı vlastnost: pro kaˇzd´e n ∈ N existuje R(n) > 0 takov´e, ˇze kaˇzd´e podslovo slova u d´elky R(n) obsahuje vˇsechny faktory slova u d´elky n.
Nekoneˇ cn´ a slova jako model kvazikrystal˚ u C´ılem t´eto kapitoly je charakterizovat skupinu nekoneˇcn´ych slov, kter´a jsou vhodn´ym modelem kvazikrystal˚ u. K tomutu u ´ˇcelu je nejprve nutno zav´est nˇekolik pojm˚ u. R´ enyiho rozvoj jedniˇ cky a Parryho ˇ c´ısla Nechˇt β > 1, potom Tβ je zobrazen´ı definovan´e pro kaˇzd´e x ∈ [0, 1] P pˇredpisem −i ˇ Tβ (x) := βx − ⌊βx⌋. Necht β > 1 a x ∈ [0, 1). Reprezentace x = i≥1 ti β , kde ti ∈ N, se naz´yv´a R´enyiho rozvoj x v b´azi β, pokud pro koeficienty plat´ı: ti := ⌊βTβi−1 (x)⌋. Kaˇzd´e β > 1 je charakterizov´ano sv´ym R´enyiho rozvojem jedniˇcky, znaˇcen´ym dβ (1) = t1 t2 . . . , kde ti := ⌊βTβi−1 (1)⌋. Pokud dβ (1) je posloupnost periodick´a od urˇcit´eho ˇclenu, β se naz´yv´a Parryho ˇc´ıslo. Pokud dβ (1) je koneˇcn´a posloupnost, β se naz´yv´a jednoduch´e Parryho ˇc´ıslo. Nechˇt dβ (1) je periodick´a od urˇcit´eho ˇclenu, speci´alnˇe nechˇt m ∈ N a p ∈ N jsou minim´aln´ı takov´a, ˇze dβ (1) = t1 ...tm (tm+1 ...tm+p )ω . Substituce ϕ = ϕβ pˇridruˇzen´a β je definovan´a na abecedˇe {0, 1, ..., m + p − 1} pˇredpisem ϕ(0) = 0t1 1, . . . , ϕ(m + p − 2) = 0tm+p−1 (m + p − 1), ϕ(m + p − 1) = 0tm+p m. (1) Nekoneˇcn´e slovo pˇridruˇzen´e β je pevn´y bod uβ = limn→∞ ϕn (0) substituce ϕ. (Jelikoˇz ϕn (0) je vlastn´ı pˇredponou ϕn+1 (0), nov´e a nov´e aplikov´an´ı substituˇcn´ıho pˇredpisu skuteˇcnˇe vytvoˇr´ı nekoneˇcn´e slovo.)
β-rozvoj a β-cel´ aˇ c´ısla Pod´ıvejme se nyn´ı na slovo uβ z algebraick´eho pohledu. Kaˇzd´y z n´as se bˇeˇznˇe ˇ setk´av´a s rozvojem ˇc´ısel v des´ıtkov´e soustavˇe. Casto je vˇsak v´yhodn´e rozv´ıjet ˇc´ısla k ˇ i v jin´ych b´az´ıch. Necht β > 1 a x ≥ 1 a x/β < 1, β-rozvojem ˇc´ısla x naz´yv´ame R´enyiho rozvoj x/β k n´asoben´y β k . Samozˇrejmˇe pro x ∈ [0, 1) definujeme β-rozvoj x jako jeho R´ enyiho Pkrozvoj.i Nez´aporn´a β-cel´a ˇc´ısla jsou pak definov´ana jako: + Zβ := {x ≥ 0 x = i=0 xi β je β-rozvoj ˇc´ısla x}. Je pˇrirozen´e definovat pak β+ cel´a ˇc´ısla jako: Zβ = −Z+ a ˇc´ısla tedy hraj´ı v oblasti nestandardn´ıch β ∪ Zβ . β-cel´ ˇc´ıseln´ych syst´em˚ u stejnˇe v´yznamnou roli jako cel´a ˇc´ısla pˇri rozvoji v des´ıtkov´e soustavˇe. Nechˇt dβ (1) je periodick´a od urˇcit´eho ˇclenu, speci´alnˇe nechˇt m ∈ N a p ∈ N jsou minim´aln´ı takov´a, ˇze dβ (1) = t1 ...tm (tm+1 ...tm+p )ω . Potom existuje pr´avˇe m + p mezer mezi po sobˇe jdouc´ımi β-cel´ymi ˇc´ısly. Pˇriˇrad´ıme-li mezer´am p´ısmena 0, 1, . . . , m + p − 1 podle velikosti (nejvˇetˇs´ı mezeˇre ˇc´ıslo 0, aˇz nejmenˇs´ı m + p − 1), z´ısk´ame pr´avˇe nekoneˇcn´e slovo uβ , tedy pevn´y bod substituce ϕ. Zpˇ et ke kvazikrystal˚ um Nyn´ı, kdyˇz se na nekoneˇcn´e slovo uβ m˚ uˇzeme d´ıvat jako na k´odov´an´ı algebraick´e struktury Zβ , lze hledat souvislost s kvazikrystalickou strukturou. Thurston [7] uk´azal, ˇze pro Parryho ˇc´ıslo β je Zβ stejnomˇernˇe diskr´etn´ı a relativnˇe hust´a mnoˇzina, tj. delonovsk´a mnoˇzina [5]. Pro β, kter´e je nav´ıc Pisotovo, vyhovuje Zβ meyerovsk´e podm´ınce: Zβ − Zβ ⊂ Zβ + F pro koneˇcnou mnoˇzinu F . Pˇripomeˇ nme, ˇze Pisotovo ˇc´ıslo je algebraick´e cel´e ˇc´ıslo, jehoˇz vˇsechny sdruˇzen´e koˇreny jsou v absolutn´ı hodnotˇe ostˇre menˇs´ı neˇz jedna. Delonovsk´e mnoˇziny splˇ nuj´ıc´ı meyerovskou podm´ınku jsou vhodn´ymi modely kvazikrystal˚ u, a tedy β-cel´a ˇc´ısla pro β Pisotovo ˇc´ıslo slouˇz´ı jako 1-dimenzion´aln´ı model kvazikrystal˚ u. V pˇr´ıpadˇe kvadratick´ych algebraick´ych ˇc´ısel spl´yv´a pojem Parryho a Pisotova ˇc´ısla. Tedy zkoum´ame-li nekoneˇcn´a slova, kter´a odpov´ıdaj´ı kvadratick´emu Parryho ˇc´ıslu (a to je pr´avˇe pˇr´ıpad, kter´y n´as bude zaj´ımat), studujeme nepˇr´ımo jednodimenzion´aln´ı kvazikrystaly.
Jazyky uzavˇ ren´ e na reverzi V t´eto kapitole vysvˇetl´ıme, proˇc se pˇri zkoum´an´ı palindromick´e komplexity staˇc´ı zamˇeˇrit na nekoneˇcn´a slova pˇridruˇzen´a kvadratick´emu Parryho ˇc´ıslu. V ˇcl´anku [3] je moˇzno nal´ezt d˚ ukaz n´asleduj´ıc´ıch dvou tvrzen´ı. 1. Nechˇt u je nekoneˇcn´e stejnomˇernˇe rekurentn´ı slovo (a to pevn´e body primitivn´ı substituce jsou). Pak pokud v jazyce L(u) existuje palindrom d´elky > n pro kaˇzd´e n ∈ N, potom je L(u) uzavˇren´y na reverzi, tj. s kaˇzd´ym slovem obsahuje i jeho zrcadlov´y obraz. 2. Nechˇt uβ je pevn´ym bodem substituce (1). Jazyk L(uβ ) je uzavˇren´y na reverzi tehdy a jen tehdy, kdyˇz m = p = 1, tj. ϕ(0) = 0t1 1, ϕ(1) = 0t2 1. Budeme zkoumat nekoneˇcn´e slovo uβ , kter´e je pevn´ym bodem substituce ϕ(0) = 0a 1, ϕ(1) = 0b 1, kde 1 ≤ b < a, tj. substituce odpov´ıdaj´ıc´ı dβ (1) = abω , protoˇze z pˇredchoz´ıch tvrzen´ı vypl´yv´a, ˇze v jin´ych pˇr´ıpadech Parryho ˇc´ısel obsahuje nekoneˇcn´e slovo uβ jen koneˇcnˇe mnoho palindrom˚ u.
Komplexita Poznamenejme, ˇze pro jednoduch´a Parryho ˇc´ısla byla komplexita vyˇsetˇrena v [4] a d˚ ukazy tvrzen´ı t´eto kapitoly je moˇzno nal´ezt v [2]. Prvn´ım krokem k urˇcen´ı palindromick´e komplexity uβ je nalezen´ı jeho komplexity. Faktorov´a komplexita (nebo jednoduˇse komplexita) je funkce C : N ⇒ N definovan´a pˇredpisem C(n) = poˇcet r˚ uzn´ych faktor˚ u d´elky n. Jednoduch´ym pozorov´an´ım je n´asleduj´ıc´ı fakt. Nechˇt Mn je mnoˇzina lev´ych speci´aln´ıch faktor˚ u jazyka L(uβ ) d´elky n. Potom C(n + 1) − C(n) = #Mn . Zamˇeˇrme se tedy na lev´e speci´aln´ı faktory. Je jich nˇekolik druh˚ u. • Lev´y speci´aln´ı faktor v ∈ L(uβ ) se naz´yv´a maxim´aln´ı, pokud ani v0 ani v1 nejsou lev´e speci´aly. • Nekoneˇcn´e slovo u se naz´yv´a nekoneˇcn´y lev´y speci´aln´ı faktor uβ , pokud kaˇzd´a pˇredpona u je lev´ym speci´aln´ım faktorem L(uβ ). • Faktor v se naz´yv´a tot´alnˇe bispeci´aln´ı, pokud jak v0 tak v1 jsou lev´e speci´aln´ı faktory uβ . Zˇrejm´e je, ˇze kaˇzd´y lev´y speci´aln´ı faktor je pˇredponou maxim´aln´ıho nebo nekoneˇcn´eho lev´eho speci´aln´ıho faktoru. M´ame tedy n´avod, kter´y ˇr´ık´a, ˇze je tˇreba vyˇsetˇrit maxim´aln´ı a nekoneˇcn´e lev´e speci´aln´ı faktory. Provedeme-li to, z´ısk´ame n´asleduj´ıc´ı v´ysledky pro pˇr´ıpad, kdy dβ (1) = abω a b < a − 1: • Vˇsechny tot´alnˇe bispeci´aln´ı faktory maj´ı tvar: V (1) = 0b , V (n) = 0b 1ϕ(V n−1) )0b pro n > 1. Nav´ıc, V (n−1) je pˇredponou V (n) pro kaˇzd´e n ∈ N. • Existuje jedin´y nekoneˇcn´y lev´y speci´aln´ı faktor limn→∞ V (n) . • Vˇsechny maxim´aln´ı lev´e speci´aln´ı faktory maj´ı tvar: U (1) = 0a−1 , U (n) = 0b 1ϕ(U (n−1) )0b pro n > 1. Nav´ıc, V (n) je pˇredponou U (n) pro kaˇzd´e n ∈ N. Situaci m˚ uˇzeme zn´azornit pomoc´ı stromu lev´ych speci´aln´ıch faktor˚ u. Ten se skl´ad´a (n) z jedn´e nekoneˇcn´e vˇetve (limn→∞ V ) a z n´ı se odˇstˇepuj´ıc´ıch vˇetv´ı, kter´e odpov´ıdaj´ı maxim´aln´ım lev´ym speci´aln´ım faktor˚ um U (n) . K vˇetven´ı doch´az´ı v tot´alnˇe bispeci´aln´ıch faktorech V (n) . Kaˇzd´y lev´y speci´aln´ı faktor je pˇredponou tohoto stromu. Z tˇechto u ´ vah uˇz snadno plyne vzorec pro komplexitu. Vˇ eta 1. Komplexita pro dβ (1) = abω , b < a − 1, splˇ nuje pro kaˇzd´e n ∈ N, 2 |V (k) | < n ≤ |U (k) | pro k ∈ N, △C(n) = C(n + 1) − C(n) = 1 jinak. ˇ Uvedme pro ilustraci strom lev´ych speci´aln´ıch faktor˚ u pro uβ , kter´e je pevn´ym ω bodem ϕ(0) = 0001, ϕ(1) = 01, tedy kde dβ (1) = 31 . V tomto stromˇe vid´ıme vˇsechny lev´e speci´aln´ı faktory do d´elky 14.
U(2) = 01000100010
U (1) = 00 0 1
ε
0 0
1
0
0
0
1
V(1) =0
0
0
1
0
1
0
0
0
0 1
0
0
...
V(2) = 0100010
Poznamenejme, ˇze pro nekoneˇcn´e slovo uβ , kde dβ (1) = a(a − 1)ω , zjist´ıme, ˇze neexistuje ˇz´adn´y maxim´aln´ı lev´y speci´aln´ı faktor. Strom lev´ych speci´aln´ıch faktor˚ u se v tomto pˇr´ıpadˇe skl´ad´a z jedin´e nekoneˇcn´e vˇetve. Dost´av´ame C(n) = n + 1. Jde o sturmovsk´e slovo, tj. neperiodick´e slovo s nejmenˇs´ı moˇznou komplexitou.
Palindromick´ a komplexita Poznamenejme, ˇze palindromick´a komplexita pro slova pˇridruˇzen´a jednoduch´ym Parryho ˇc´ısl˚ um byla studov´ana v [1] a d˚ ukazy a podrobnosti z t´eto kapitoly naleznete v [3]. Palindromick´a komplexita je funkce P : N ⇒ N definovan´a pˇredpisem P (n) = poˇcet r˚ uzn´ych palindrom˚ u d´elky n. Vyˇreˇsme hned na zaˇc´atku pˇr´ıpad ω dβ (1) = a(a − 1) , kdy uβ je sturmovsk´e slovo. Pro sturmovsk´a slova bylo dok´az´ano, ˇze P (2n) = P (0) = 1 a P (2n + 1) = P (1) = 2 pro vˇsechna n ∈ N. Nikoho nepˇrekvap´ı, ˇze k vyˇsetˇren´ı hodnot palindromick´e komplexity je tˇreba rozliˇsit nˇekolik druh˚ u palindrom˚ u. • Palindrom p ∈ L(uβ ) se naz´yv´a maxim´aln´ı, pokud 0p0 6∈ L(uβ ) a 1p1 6∈ L(uβ ). • Nechˇt v = ...v3 v2 v1 je doleva nekoneˇcn´e slovo na abecedˇe {0, 1}. Oznaˇcme v = v1 v2 v3 .... Nechˇt d ∈ {ε, 0, 1}. Pokud pro kaˇzd´e n ∈ N je slovo p = vn vn−1 ...v1 dv1 v2 ...vn ∈ L(uβ ), potom vdv se naz´yv´a nekoneˇcn´a palindromick´a vˇetev uβ se stˇredem d. Je jasn´e, ˇze kaˇzd´y palindrom je centr´aln´ım faktorem maxim´aln´ıho palindromu nebo nekoneˇcn´e palindromick´e vˇetve. • Palindrom p je maxim´aln´ı palindrom ⇔ p = U (n) , tedy maxim´aln´ımu lev´emu speci´aln´ımu faktoru, pro nˇejak´e pˇrirozen´e ˇc´ıslo n. (Pˇresvˇedˇcte se na obr´azku, ˇze U (1) a U (2) jsou palindromy.) • Pro kaˇzd´e d ∈ {ε, 0, 1} existuje nejv´yˇse jedna nekoneˇcn´a palindromick´a vˇetev se stˇredem d. ˇ Uvedme jeˇstˇe vzorec, kter´y umoˇzn ˇ uje vyuˇz´ıt komplexity k v´ypoˇctu palindromick´e komplexity. Vˇ eta 2. Pro palindromickou komplexitu uβ , kde dβ (1) = abω , b < a − 1, plat´ı P (n + 1) + P (n) = △C(n) + 2 pro kaˇzd´e n ∈ N. A tedy plat´ı: P (2n + 1) = △C(2n) + 2 − P (2n).
Z posledn´ıho tvrzen´ı vypl´yv´a, ˇze pˇri zkoum´an´ı palindromick´e komplexity se staˇc´ı omezit na hled´an´ı jej´ı hodnoty napˇr´ıklad jen pro sud´a ˇc´ısla. Existuj´ı 4 r˚ uzn´e vzorce pro palindromickou komplexitu v z´avislosti na sudosti ˇci lichosti parametr˚ u a a b. Pro ilustraci uvedeme v´ysledky pro pˇr´ıpad, kdy a i b jsou lich´a ˇc´ısla. • Existuje nekoneˇcn´a palindromick´a vˇetev se stˇredem 0, oboustrann´a limita palindrom˚ u V (n) , tedy n´am zn´am´ych tot´alnˇe bispeci´an´ıch faktor˚ u. Jin´e nekoneˇcn´e palindromick´e vˇetve neexistuj´ı. • Existuje jedin´y maxim´aln´ı palindrom sud´e d´elky, jedin´y maxim´aln´ı palindrom se stˇredem 1 a nekoneˇcnˇe mnoho maxim´aln´ıch palindrom˚ u se stˇredem 0. U (1) = 0(a−1) se stˇredem ε. U (2) se stˇredem 1. U (n) se stˇredem 0 a s centr´aln´ım faktorem V (n−2) , pro n ≥ 3. Pˇripomeˇ nme vˇetu 2, kter´a ˇr´ık´a, ˇze pro v´ypoˇcet palindromick´e komplexity staˇc´ı vˇedˇet, ˇze existuje jedin´y maxim´aln´ı palindrom sud´e d´elky a ˇze neexistuje nekoneˇcn´a palindromick´a vˇetev se stˇredem ε.
Z´ avˇ er C´ılem tohoto ˇcl´anku nebylo uv´est pˇresn´e vzorce faktorov´e a palindromick´e komplexity, ale popsat n´astroje, kter´e umoˇzn´ı zkoumat tyto charakteristiky i pro jin´a stejnomˇernˇe rekurentn´ı nekoneˇcn´a slova, kter´a mohou modelovat jin´a fenomena neˇz kvazikrystaly, tˇreba posloupnosti k´oduj´ıc´ı genetickou informaci.
References [1] P. Ambroˇz, Ch. Frougny, Z. Mas´akov´a, E. Pelantov´a, Palindromic complexity of infinite words associated with simple Parry numbers, to appear in Annales de l’Institut Fourier (2005) [2] L. Balkov´a, Complexity for infinite words associated with quadratic non-simple Parry numbers, to appear in J. Geom. Sym. Phys. WGMP Proceedings (2005) [3] L. Balkov´a, Palindromic complexity of infinite words associated with quadratic non-simple Parry numbers, to appear in J. Theor. Comp. Science (2006) [4] Ch. Frougny, Z. Mas´akov´a, E. Pelantov´a, Complexity of infinite words associated with beta-expansions, RAIRO Theor. Inform. Appl. 38 (2004), 163-185 [5] J. Lagarias, Geometric models for quasicrystals I. Delone sets of finite type, Discrete Comput. Geom. 21 (1999), 161-191 [6] D. Shechtman, I. Blech, D. Gratias, and J. Cahn, Metallic phase with longrange orientational order and no translational symmetry, Phys. Rev. Lett. 53 (1984), 1951-1954 [7] W. P. Thurston, Groups, tilings, and finite state automata, Geom. supercomp. project research report GCG1, University of Minnesota (1989)
