Almost periodic sequences

✍ Scribed by An. Muchnik; A. Semenov; M. Ushakov

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 384 KB
• Volume: 304
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00847-2

✦ Synopsis

This paper studies properties of almost periodic sequences (also known as uniformly recursive). A sequence is almost periodic if for every ÿnite string that ccurs inÿnitely many times in the sequence there exists a number m such that every segment of length m contains an ccurrence of the word.

We study closure properties of the set of almost periodic sequences, ways to generate such sequences (including a general way), computability issues and Kolmogorov complexity of preÿxes of almost periodic sequences.