Aperiodicity measure for infinite sequences

Yuri Pritykin; Julya Ulyashkina

doi:10.1007/978-3-642-03351-3_26

Aperiodicity measure for infinite sequences

Yuri Pritykin, Julya Ulyashkina

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings
Pages	274-285
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-03351-3_26
State	Published - 2009
Externally published	Yes
Event	4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Russian Federation Duration: Aug 18 2009 → Aug 23 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5675 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Computer Science Symposium in Russia, CSR 2009
Country/Territory	Russian Federation
City	Novosibirsk
Period	8/18/09 → 8/23/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Pritykin, Y., & Ulyashkina, J. (2009). Aperiodicity measure for infinite sequences. In Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings (pp. 274-285). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5675 LNCS). https://doi.org/10.1007/978-3-642-03351-3_26

@inproceedings{a36a68970b5a4c01986ded0e2732d729,

title = "Aperiodicity measure for infinite sequences",

abstract = "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.",

author = "Yuri Pritykin and Julya Ulyashkina",

year = "2009",

doi = "10.1007/978-3-642-03351-3_26",

language = "English (US)",

isbn = "3642033504",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "274--285",

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

note = "4th International Computer Science Symposium in Russia, CSR 2009 ; Conference date: 18-08-2009 Through 23-08-2009",

}

Pritykin, Y & Ulyashkina, J 2009, Aperiodicity measure for infinite sequences. in Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5675 LNCS, pp. 274-285, 4th International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russian Federation, 8/18/09. https://doi.org/10.1007/978-3-642-03351-3_26

Aperiodicity measure for infinite sequences. / Pritykin, Yuri; Ulyashkina, Julya.
Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. 2009. p. 274-285 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5675 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Pritykin Y, Ulyashkina J. Aperiodicity measure for infinite sequences. In Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. 2009. p. 274-285. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03351-3_26

Aperiodicity measure for infinite sequences

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this