Combinatorical and Algebraic Structures Seminar

Session details

Date: 19.10.2010
Speaker: Ľubomíra Balková a Štěpán Starosta, FJFI, České vysoké učení technické v Praze
Title: Nekonečná slova s konečným defektem
Abstract: Defekt konečného slova $w$ je rozdíl mezi maximálním možným počtem palindromů (což je $|w|+1$) a počtem různých palindromů obsažených ve slově $w$. Definici lze rozšířit na nekonečná slova. Na semináři pohovoříme o různých známých charakterizacích stejnoměrně rekurentních slov, která mají konečný defekt, a nové charakterizaci pomocí vztahu mezi palindromickou a faktorovou komplexitou. Dále zavedeme třídu morfizmů Pret uzavřenou na skládání a ukážeme, že stejnoměrně rekurentní slova jsou obrazem bohatých slov (rich words) pro morfizmy třídy Pret. Třída Pret úzce souvisí s dobře známou třídou $P$ definovanou Hofem, Knillem a Simonem: každý morfizmus třídy Pret je konjugovaný k morfizmu třídy $P$.
Slides: 20101019.pdf

Return to index.