Combinatorical and Algebraic Structures Seminar

Session details

Date: 24.11.2006
Speaker: Štěpán Starosta, FJFI, České vysoké učení technické
Title: Bispeciální faktory a komplexita
Abstract: V množině všech faktorů daného nekonečného slova $u$ hrají důležitou roli tak zvané bispeciální faktory. Ukážeme, jak je možné jich využít při výpočtu komplexity slova $u$, tj. funkce udávající počet faktorů dané délky slova $u$. Pro dvouprvkovou abecedu spočítáme za pomoci odvozených nastrojů komplexitu slova definovaného jako pevný bod daného morfismu. Dále uvedeme tvrzení charakterizující funkce, které mohou být komplexitou nějakého slova.

Return to index.