Aperiodicity measure for infinite sequences

Yuri Pritykin, Julya Ulyashkina

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationComputer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings
Pages274-285
Number of pages12
DOIs
StatePublished - 2009
Event4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Russian Federation
Duration: Aug 18 2009Aug 23 2009

Publication series

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

Conference

Conference4th International Computer Science Symposium in Russia, CSR 2009
Country/TerritoryRussian Federation
CityNovosibirsk
Period8/18/098/23/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Aperiodicity measure for infinite sequences'. Together they form a unique fingerprint.

Cite this