Sequences close to periodic. (English. Russian original) Zbl 1208.03017

Muchnik, An. A.; Pritykin, Yu. L.; Semenov, A. L.

Russ. Math. Surv. 64, No. 5, 805-871 (2009); translation from Usp. Mat. Nauk 64, No. 5, 21-96 (2009).

As is already said in the abstract, the paper is a survey of concepts and results connected with generalizations of the notion of periodic sequence, both classical and new ones. Almost periodicity is related to different areas, such as combinatorics on words, symbolic dynamics, expressibility in logical theories, computability, and number theory.
At the begining, two classical examples are analyzed: on the one hand the Thue-Morse sequences, and on the other hand the Sturmian sequences and the Fibonacci sequence.
In the second section, a universal method for constructing generalized almost periodic sequences is described. The method has been first developed by Semenov in a paper concerned with logical theories of unary functions on the set of natural numbers. The method has been further developed in a framework closer to the paper under review in a later joint work with Ushakov and Muchnik.
In the third section, the authors study relations with logic: with automata, and further with questions on the decidability of theories of specific sequences. The results here are of the following type: the theory of an almost periodic sequence is decidable if and only if the sequence is computable and the set of subwords is decidable. As an application, the theory of the Thue-Morse sequence is decidable, and the theory of a Sturmian sequence with slope \(a\) and shift \(b\) is decidable if and only if \(a\) and \(b\) are computable numbers.
Section 4 is dedicated to undecidable properties of almost periodic sequences. In contrast to this section, Section 5 presents relationships with automatic and morphic sequences, and in particular with many problems that are algorithmically solvable. To give an example, there is a polynomial-time algorithm that, given an automatic sequence, decides if it is almost periodic. In a subsection, real numbers are studied according to their infinite numeric representations. It is known that a Sturmian sequence always denotes a transcendental number, but many conjectures in this direction are still open questions.
In Section 6, the authors consider the Kolmogorov complexity of almost periodic sequences, and they introduce also other complexity measures, e.g., a measure of aperiodicity. There are many remarkable results concerning this measure. Its value is 0 for a Sturmian sequence, 1/2 for a random binary sequence, and 1/3 for the Thue-Morse sequence.
The last section is dedicated to alternative approaches to the closeness to periodicity. The Toeplitz and the Kolakoski sequences are the most important examples discussed here.

Reviewer: Mihai Prunescu (Freiburg i. Br.)

MSC:

03B25	Decidability of theories and sets of sentences
03D03	Thue and Post systems, etc.
03D05	Automata and formal grammars in connection with logical questions
03D40	Word problems, etc. in computability and recursion theory
11B75	Other combinatorial number theory
68Q30	Algorithmic information theory (Kolmogorov complexity, etc.)
68R15	Combinatorics on words

Keywords:

combinatorial on words; symbolic dynamics; automata; decidability of logical theories; almost periodic sequence; morphic sequence; Thue-Morse sequence; Fibonacci sequence; Sturmian sequence; complexity of a sequence; monadic theories; normal numbers; tiling periodicity; Toeplitz sequences; Kolakoski sequence; Kolmogorov complexity; survey paper