SEMINARIO DI
MATEMATICA
ore
14.00
Scuola Normale
Superiore
Pisa
(Sala Riunioni, Collegio
Puteano)
Dong
Han KIM
University
of Suwon, Korea
Terrà un seminario dal
titolo:
“Return time complexity of Sturmian
sequences”
Abstract
The
Sturmian sequence has the lowest subword complexity besides periodic
sequences.
Let
$R_n(x)$ be the recurrence time of initial $n$-word of an infinite sequence $x$.
We
have that $x$ is periodic if and only if there is $M$ such that $R_n(x) \le n$
for all $n > M$.
Therefore,
for nonperiodic sequences $R_n(x) \le n +1$ is the possible lowest upper bound for
$R_n$.
We
show that if $R_n(x) \le n +1$ for all $n$, then $x$ is a Strumian
sequence.
In
general, the opposite does not holds and we completely classify the such
Sturmian sequences.
Tutti gli interessati
sono invitati a partecipare.
Classe
di Scienze