TY - GEN

T1 - Aperiodicity measure for infinite sequences

AU - Pritykin, Yuri

AU - Ulyashkina, Julya

PY - 2009

Y1 - 2009

N2 - We introduce the notion of aperiodicity measure for infinite symbolic sequences. Informally speaking, the aperiodicity measure of a sequence is the maximum number (between 0 and 1) such that this sequence differs from each of its non-identical shifts in at least fraction of symbols being this number. We give lower and upper bounds on the aperiodicity measure of a sequence over a fixed alphabet. We compute the aperiodicity measure for the Thue-Morse sequence and its natural generalization the Prouhet sequences, and also prove the aperiodicity measure of the Sturmian sequences to be 0. Finally, we construct an automatic sequence with the aperiodicity measure arbitrarily close to 1.

AB - We introduce the notion of aperiodicity measure for infinite symbolic sequences. Informally speaking, the aperiodicity measure of a sequence is the maximum number (between 0 and 1) such that this sequence differs from each of its non-identical shifts in at least fraction of symbols being this number. We give lower and upper bounds on the aperiodicity measure of a sequence over a fixed alphabet. We compute the aperiodicity measure for the Thue-Morse sequence and its natural generalization the Prouhet sequences, and also prove the aperiodicity measure of the Sturmian sequences to be 0. Finally, we construct an automatic sequence with the aperiodicity measure arbitrarily close to 1.

UR - http://www.scopus.com/inward/record.url?scp=70350347959&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350347959&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03351-3_26

DO - 10.1007/978-3-642-03351-3_26

M3 - Conference contribution

AN - SCOPUS:70350347959

SN - 3642033504

SN - 9783642033506

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 274

EP - 285

BT - Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings

T2 - 4th International Computer Science Symposium in Russia, CSR 2009

Y2 - 18 August 2009 through 23 August 2009

ER -