Combinatorical and Algebraic Structures Seminar
Session details
Date: | 3.5.2016 |
Speaker: | Josef Florian, FJFI, České vysoké učení technické v Praze |
Title: | Nekonečná slova s komplexitou $2n$ |
Abstract: | V příspěvku bude představena konstrukce nekonečných slov s komplexitou $2n$ podle článku Güntra Roteho: Sequences with Subword Complexity $2n$ z roku 1992. Komplexita nějakého nekonečného slova $\mathbf{u}$ je zobrazení $\mathcal{C}_{\mathbf{u}}: \mathbb{N} \rightarrow \mathbb{N}$, pro které platí $\mathcal{C}_{\mathbf{u}}(n)=$ počet faktorů slova $\mathbf{u}$ délky $n$. Představíme si obecný algoritmus pro konstrukci nekonečných slov s komplexitou $2n$ založený na použití orientovaných grafů a poté si ukážeme několik konkrétnějších způsobů, kterými je možno taková slova vyrobit. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož