On Almost Periodicity Criteria for Morphic Sequences
in Some Particular Cases
Yuri Pritykin∗
November 4, 2018
Abstract
In some particular cases we give criteria for morphic sequences to be almost periodic (=uni-
formly recurrent). Namely, we deal with fixed points of non-erasing morphisms and with auto-
matic sequences. In both cases a polynomial-time algorithm solving the problem is found. A
result more or less supporting the conjecture of decidability of the general problem is given.
1 Introduction
Different problems of decidability in combinatorics on words are always of great interest and dif-
ficulty. Here we deal with two main types of symbolic infinite sequences — morphic and almost
periodic — and try to understand connections between them. Namely, we are trying to find an
algorithmic criterion which given a morphic sequence decides whether it is almost periodic.
Though the main problem still remains open, we propose polynomial-time algorithms solving
the problem in two important particular cases: for pure morphic sequences generated by non-erasing
morphisms (Section 3) and for automatic sequences (Section 4). In Section 5 we say a few words
about connections with monadic logics. In particular, in a curious result of Corollary 4 we give a
reason why the main problem may be decidable.
Some attempts to solve the problem were already done. In [3] A. Cobham gives a criterion for
automatic sequence to be almost periodic. But even if his criterion gives some effective procedure
solving the problem (which is not clear from his result, and he does not care about it at all), this
procedure could not be fast. We construct a polynomial-time algorithm solving the problem. In [5]
A. Maes deals with pure morphic sequences and finds a criterion for them to belong to a slightly
different class of generalized almost periodic sequences (but he calls them almost periodic — see
[9] for different definitions). And again, his algorithm does not seem to be polynomial-time.
All the results of this paper can be found in [10].
2 Preliminaries
Denote the set of natural numbers {0, 1, 2, . . . } by N and the binary alphabet {0, 1} by B. Let A
be a finite alphabet. We deal with sequences over this alphabet, i. e., mappings x : N → A, and
denote the set of these sequences by AN.
∗Moscow State University, Russia, http://lpcs.math.msu.su/~pritykin/, yura@mccme.ru. The work was par-
tially supported by RFBR grants 06-01-00122, 05-01-02803, Kolmogorov grant of Institute of New Technologies, and
August Möbius grant of Independent University of Moscow.
http://arxiv.org/abs/0704.0218v1
Denote by A∗ the set of all finite words over A including the empty word Λ. If i ≤ j are natural,
denote by [i, j] the segment of N with ends in i and j, i. e., the set {i, i + 1, i + 2, . . . , j}. Also
denote by x[i, j] a subword x(i)x(i + 1) . . . x(j) of a sequence x. A segment [i, j] is an occurrence
of a word u ∈ A∗ in a sequence x if x[i, j] = u. We say that u 6= Λ is a factor of x if u occurs in x.
A word of the form x[0, i] for some i is called prefix of x, and respectively a sequence of the form
x(i)x(i+ 1)x(i+ 2) . . . for some i is called suffix of x and is denoted by x[i,∞). Denote by |u| the
length of a word u. The occurrence u = x[i, j] in x is k-aligned if k|i.
A sequence x is periodic if for some T we have x(i) = x(i+ T ) for each i ∈ N. This T is called
a period of x. We denote by P the class of all periodic sequences. Let us consider an extension of
this class.
A sequence x is called almost periodic1 if for every factor u of x there exists a number l such
that every factor of x of length l contains at least one occurrence of u (and therefore u occurs in x
infinitely many times). Obviously, to show almost periodicity of a sequence it is sufficient to check
the mentioned condition only for all prefixes but not for all factors (and even for some increasing
sequence of prefixes only). Denote by AP the class of all almost periodic sequences.
Let A, B be finite alphabets. A mapping φ : A∗ → B∗ is called a morphism if φ(uv) = φ(u)φ(v)
for all u, v ∈ A∗. A morphism is obviously determined by its values on single-letter words. A
morphism is non-erasing if |φ(a)| > 1 for each a ∈ A. A morphism is k-uniform if |φ(a)| = k for
each a ∈ A. A 1-uniform morphism is called a coding. For x ∈ AN denote
φ(x) = φ(x(0))φ(x(1))φ(x(2)) . . .
Further we consider only morphisms of the form A∗ → A∗ (but codings are of the form A → B,
which in fact does not matter, they can be also of the form A→ A without loss of generality). Let
φ(s) = su for some s ∈ A, u ∈ A∗. Then for all natural m < n the word φn(s) begins with the word
φm(s), so φ∞(s) = limn→∞ φ
n(s) = suφ(u)φ2(u)φ3(u) . . . is well-defined. If ∀n φn(u) 6= Λ, then
φ∞(s) is infinite. In this case we say that φ is prolongable on s. Sequences of the form h(φ∞(s))
for a coding h : A→ B are called morphic, of the form φ∞(a) are called pure morphic.
Notice that there exist almost periodic sequences that are not morphic (in fact, the set of almost
periodic sequences has cardinality continuum, while the set of morphic sequences is obviously
countable), as well as there exist morphic sequences that are not almost periodic (you will find
examples later). Our goal is to determine whether a morphic sequence is almost periodic or not
given its constructive definition.
First of all, observe the following
Lemma 1. A sequence φ∞(s) is almost periodic iff s occurs in this sequence infinitely many times
with bounded distances.
Proof. In one direction the statement is obviously true by definition.
Suppose now that s occurs in φ∞(s) infinitely many times with bounded distances. Then for
every m the word φm(s) also occurs in φ∞(s) infinitely many times with bounded distances. But
every word u occurring in φ∞(s) occurs in some prefix φm(s) and thus occurs infinitely many times
with bounded distances.
For a morphism φ : {1, . . . , n} → {1, . . . , n} we can define a corresponding matrix M(φ), such
that M(φ)ij is a number of occurrences of symbol i into φ(j). One can easily check that for each l
we have M(φ)l =M(φl).
Morphism φ is called primitive if for some l all the numbers in M(φl) are positive.
1It was called strongly or strictly almost periodic in [7, 8].
Let us construct an oriented graph G corresponding to a morphism. Let its set of vertices be
A. In G edges go from b ∈ A to all the symbols occurring in φ(b).
For φ∞(s) it can easily be found using the graph corresponding to φ which symbols from A
really occur in this sequence. Indeed, these symbols form the set of all vertices that can be reached
from s. So without loss of generality from now on we assume that all the symbols from A occur in
φ∞(s).
A morphism is primitive if and only if its corresponding graph is strongly connected, i. e., there
exists an oriented path between every two vertices. This reformulation of the primitiveness notion
seems to be more appropriate for computational needs.
By Lemma 1 (and the observation that codings preserve almost periodicity) morphic sequences
obtained by primitive morphisms are always almost periodic. Moreover, in the case of increasing
morphisms (such that |φ(b)| > 2 for each b) this sufficient condition is also necessary (and this
is a polynomial-time algorithmic criterion). However when we generalize this case even on non-
erasing morphisms, it is not enough to consider only the corresponding graph or even the matrix
of morphism (which has more information), as it can be seen from the following example.
Let φ1 be as follows: 0 → 01, 1 → 120, 2 → 2, and φ2 be as follows: 0 → 01, 1 → 210, 2 → 2.
Then these two morphisms have identical matrices of morphism, but φ∞1 (0) is almost periodic, while
φ∞2 (0) is not. Indeed, in φ
2 (0) there are arbitrary long segments like 222. . . 22, so φ
2 (0) /∈ AP .
There is no such problem in φ∞1 (0). Since 0 occurs in both φ1(0) and φ1(1), and 22 does not occur
in φ∞1 (0), it follows that 0 occurs in φ
1 (0) with bounded distances. Thus φ
1 (0) for every m > 0
occurs in φ∞1 (0) with bounded distances, so φ
1 (0) ∈ AP. See Theorem 1 for a general criterion of
almost periodicity in the case of fixed points of non-erasing morphisms.
To introduce a bit the notion of almost periodicity, let us formulate an interesting result on this
topic. It seems to be first proved in [3], but also follows from the results of [9]. For x ∈ AN, y ∈ BN
define x× y ∈ (A×B)N such that (x× y)(i) = 〈x(i), y(i)〉.
Proposition 1. If x is almost periodic and y is periodic, then x× y is almost periodic.
3 Pure Morphic Sequences Generated by Non-erasing Morphisms
Here we consider the case of morphic sequence of the form φ∞(s) for non-erasing φ. We present an
algorithm that determines whether a morphic sequence φ∞(s) is almost periodic given an alphabet
A, a morphism φ and a symbol s ∈ A.
Suppose we have A, φ and s ∈ A, such that |A| = n, maxb∈A |φ(b)| = k, s begins φ(s).
Remember that we suppose that all the symbols from A appear in φ∞(s).
Divide A into two parts. Let I be the set of all symbols b ∈ A such that |φm(b)| → ∞ as
m→ ∞. Denote F = A \ I, it is the set of all symbols b such that |φm(b)| is bounded. Also define
E ⊆ F to be the set of all symbols b such that |φ(b)| = 1.
We can find a decomposition A = I ⊔ F in poly(n, k)-time as follows.
Find E. Then find all the cycles in G with all the vertices lying in E. Join all the vertices of all
these cycles in a set D. This set is stabilizing: F is the set of all vertices in G such that all infinite
paths starting from them stabilize in D. Polynomiality can be checked easily.
Construct “a graph of left tails” L with marked edges. Its set of vertices is I. From each vertex
b exactly one edge goes off. To construct this edge, find a representation φ(b) = uv, where c ∈ I,
u is the maximal prefix of φ(b) containing only symbols from F . It follows from the definitions
of I and F that u does not coincide with φ(b), that is why this representation is correct. Then
construct in L an edge from b to c and write u on it.
Analogously we construct “a graph of right tails” R. (In this case we consider representations
φ(b) = vu where u ∈ F ∗, c ∈ I.)
Now we formulate a general criterion.
Theorem 1. A sequence φ∞(s) is almost periodic iff
1) G restricted to I is strongly connected;
2) in graphs L and R on each edge of each cycle an empty word Λ is written.
It seems that full and detailed proof of this theorem can only confuse a reader, rather than a
proof sketch.
Proof sketch. By Lemma 1 for almost periodicity it is necessary and sufficient to check whether
symbol s occurs infinitely many times with bounded distances.
For every symbol b ∈ I the symbol s should occur in some φl(b), that is what the 1st part of
the criterion says.
Furthermore, in the sequence φ∞(s) all the segments of consecutive symbols from F should be
bounded. Indeed, every such segment consists only of symbols from F , but s /∈ F . That is what
the 2nd part of the criterion means, let us explain why.
Consider some v = buc occurring somewhere in φ∞(a), where b, c ∈ I, u ∈ F ∗. Every element
of sequence of words v, φ(v), φ2(v), φ3(v), . . . occurs in φ∞(s). Somewhere in the middle of φl(v) =
φl(b)φl(u)φl(c) a word φl(u) occurs. As l increases, some words from F ∗ might stick to φl(u) from
left or right for these words can come from φl(b) or φl(c). These words exactly correspond to those
written on edges of L or R. The 2nd part of the criterion exactly says that this situation can
happen only finitely many times, until we get to some cycle in L or R.
Let us consider examples with φ1 and φ2 from the end of Section 2. In both cases I = {0, 1},
F = {2}. On every edge of R in both cases Λ is written. Almost the same is true for L: the only
difference is about the edge going from 1 to 1. In the case of φ1 an empty word is written on this
edge, while in the case of φ2 a word 2 is written. That is why φ
1 (0) is almost periodic, while φ
2 (0)
is not.
Corollary 1. If for all b ∈ A we have |φ(b)| > 2, then φ∞(s) is almost periodic iff φ is primitive.
Proof. Follows from Theorem 1. In that case A = I, and on all the edges of L and R the empty
word is written.
Corollary 2. There exists a poly(n, k)-algorithm that says whether φ∞(s) is almost periodic.
Proof. Conditions from Theorem 1 can be checked in polynomial time.
It also seems useful to formulate an explicit version of the criterion for the binary case. We do
it without any additional assumptions, opposite to the previous.
Corollary 3. For non-erasing φ : B → B that is prolongable on 0 a sequence φ∞(0) is almost
periodic iff one of the following conditions holds:
1) φ(0) contains only 0s;
2) φ(1) contains 0;
3) φ(1) = Λ;
4) φ(1) = 1 and φ(0) = 0u0 for some word u.
4 Uniform Morphisms
Now we deal with morphic sequences obtained by uniformmorphisms. Again we present a polynomial-
time algorithm for solving the problem in this situation.
Suppose we have an alphabet A, a morphism φ : A∗ → A∗, a coding h : A→ B, and s ∈ A, such
that |A| = n, |B| 6 n, ∀b ∈ A |φ(b)| = k, s begins φ(s). We are interested in whether h(φ∞(s)) is
almost periodic. Sequences of the form h(φ∞(s)) with φ being k-uniform are also called k-automatic
(see [1]).
4.1 Equivalence Relations and Uniform Morphisms
For each l ∈ N define an equivalence relation on A: b ∼l c iff h(φ
l(b)) = h(φl(b)). We can easily
continue this relation on A∗: u ∼l v iff h(φ
l(u)) = h(φl(v)). In fact, this means |u| = |v| and
u(i) ∼l v(i) for all i, 1 6 i 6 |u|.
Let Bm be the Bell number, i. e., the number of all possible equivalence relations on a finite
set with exactly m elements, see [13]. As it follows from this article, we can estimate Bm in the
following way.
Lemma 2. 2m 6 Bm 6 2
Cm logm for some constant C.
Thus the number of all possible relations ∼l is not greater than Bn = 2
O(n logn). Moreover, the
following lemma gives a simple description for the behavior of these relations as l tends to infinity.
Lemma 3. If ∼r equals ∼s, then ∼r+p equals ∼s+p for all p.
Proof. Indeed, suppose ∼r equals ∼s. Then b ∼r+1 c iff φ(b) ∼r φ(c) iff φ(b) ∼s φ(c) iff b ∼s+1 c.
So if ∼r equals ∼s, then ∼r+1 equals ∼s+1, which implies the lemma statement.
This lemma means that the sequence (∼l)l∈N turns out to be ultimately periodic with a period
and a preperiod both not greater than Bn. Thus we obtain the following
Lemma 4. For some p, q 6 Bn we have for all i and all t > p that ∼t equals ∼t+iq.
4.2 Criterion
Now we are trying to get a criterion which we could check in polynomial time. Notice that the
situation is much more difficult than in the pure case because of a coding allowed. In particular,
the analogue of Lemma 1 for non-pure case does not hold.
We will move step by step to the appropriate version of the criterion reformulating it several
times.
This proposition is quite obvious and follows directly from the definition of almost periodicity
since all h(φm(a)) are the prefixes of h(φ∞(a)).
Proposition 2. A sequence h(φ∞(s)) is almost periodic iff for all m the word h(φm(s)) occurs in
h(φ∞(s)) infinitely often with bounded distances.
And now a bit more complicated version.
Proposition 3. A sequence h(φ∞(s)) is almost periodic iff for all m the symbols that are ∼m-
equivalent to s occur in φ∞(s) infinitely often with bounded distances.
Proof. ⇐. If the distance between two consecutive occurrences in φ∞(s) of symbols that are ∼m-
equivalent to s is not greater than t, then the distance between two consecutive occurrences of
h(φm(s)) in h(φ∞(s)) is not greater than tkm.
⇒. Suppose h(φ∞(s)) is almost periodic. Let ym = 012 . . . (k
m − 2)(km − 1)01 . . . (km − 1)0 . . .
be a periodic sequence with a period km. Then by Proposition 1 a sequence h(φ∞(s))×ym is almost
periodic, which means that the distances between consecutive km-aligned occurrences of h(φm(s))
in h(φ∞(s)) are bounded. It only remains to notice that if h(φ∞(s))[ikm, (i+1)km−1] = h(φm(s)),
then φ∞(s)(i) ∼m s.
Let Ym be the following statement: symbols that are ∼m-equivalent to s occur in φ
∞(s) infinitely
often with bounded distances.
Suppose for some T that YT is true. This implies that h(φ
T (s)) occurs in h(φ∞(s)) with bounded
distances. Therefore for all m 6 T a word h(φm(s)) occurs in h(φ∞(s)) with bounded distances
since h(φm(s)) is a prefix of h(φT (s)). Thus we do not need to check the statements Ym for all m,
but only for all m > T for some T .
Furthermore, it follows from Lemma 4, that we are sufficient to check the only one such state-
ment as in the following
Proposition 4. For all r > Bn: a sequence h(φ
∞(s)) is almost periodic iff the symbols that are
∼r-equivalent to s occur in φ
∞(s) infinitely often with bounded distances.
And now the final version of our criterion.
Proposition 5. For all r > Bn: a sequence h(φ
∞(s)) is almost periodic iff for some m the symbols
that are ∼r-equivalent to s occur in φ
m(b) for all b ∈ A.
Indeed, if the symbols of some set occur with bounded distances, then they occur on each
km-aligned segment for some sufficiently large m.
4.3 Polynomiality
Now we explain how to check a condition from Proposition 5 in polynomial time. We need to
show two things: first, how to choose some r > Bn and to find in polynomial time the set of all
symbols that are ∼r-equivalent to s (and this is a complicated thing keeping in mind that Bn is
exponential), and second, how to check whether for some m the symbols from this set for all b ∈ A
occur in φm(b).
Let us start from the second. Suppose we have found the set H of all the symbols that are
∼r-equivalent to s. For m ∈ N let us denote by P
m the set of all the symbols that occur in
φm(b). Our aim is to check whether exists m such that for all b we have P
m ∩H 6= ∅. First of
all, notice that if ∀b P
m ∩H 6= ∅, then ∀b P
∩H 6= ∅ for all l > m. Second, notice that the
sequence of tuples of sets ((P
m )b∈Σ)
m=0 is ultimately periodic. Indeed, the sequence (P
m=0 is
obviously ultimately periodic with both period and preperiod not greater than 2n (recall that n is
the size of the alphabet Σ). Thus the period of ((P
m )b∈Σ)
m=0 is not greater than the least common
divisor of that for (P
m=0, b ∈ A, and the preperiod is not greater than the maximal that of
m=0. So the period is not greater than (2
n)n = 2n
and the preperiod is not greater than 2n.
Third, notice that there is a polynomial-time-procedure that given a graph corresponding to some
morphism ψ (see Section 2 to recall what is the graph corresponding to a morphism) outputs a
graph corresponding to morphism ψ2. Thus after repeating this procedure n2 + 1 times we obtain
a graph by which we can easily find (P
)b∈Σ, since 2
n2+1 > 2n
+ 2n.
Similar arguments, even described with more details, are used in deciding our next problem.
Here we present a polynomial-time algorithm that finds the set of all symbols that are ∼r-equivalent
to s for some r > Bn.
We recursively construct a series of graphs Ti. Let its common set of vertices be the set of all
unordered pairs (b, c) such that b, c ∈ A and b 6= c. Thus the number of vertices is
n(n−1)
. The set
of all vertices connected with (b, c) in the graph Ti we denote by Vi(b, c).
Define a graph T0. Let V0(b, c) be the set {(φ(b)(j), φ(c)(j)) | j = 1, . . . , k, φ(b)(j) 6= φ(c)(j)}.
In other words, b ∼l+1 c if and only if x ∼l y for all (x, y) ∈ V0(b, c).
Thus b ∼2 c if and only if for all (x, y) ∈ V0(b, c) for all (z, t) ∈ V0(x, y) we have z ∼0 t. For the
graph T1 let V1(b, c) be the set of all (x, y) such that there is a path of length 2 from (b, c) to (x, y)
in T0. The graph T1 has the following property: b ∼2 c if and only if x ∼0 y for all (x, y) ∈ V1(b, c).
And even more generally: b ∼l+2 c if and only if x ∼l y for all (x, y) ∈ V1(b, c).
Now we can repeat operation made with T0 to obtain T1. Namely, in T2 let V2(b, c) be the set of
all (x, y) such that there is a path of length 2 from (b, c) to (x, y) in T1. Then we obtain: b ∼l+4 c
if and only if x ∼l y for all (x, y) ∈ V2(b, c).
It follows from Lemma 2 that log2Bn 6 Cn logn. Thus after we repeat our procedure r =
[Cn log n] times, we will obtain the graph Tl such that b ∼2r c if and only if x ∼0 y for all
(x, y) ∈ V2(b, c). Recall that x ∼0 y means h(x) = h(y), so now we can easily compute the set of
symbols that are ∼2r -equivalent to s.
5 Monadic Theories
Combinatorics on words is closely connected with the theory of second order monadic logics. Here
we just want to show some examples of these connections. More details can be found, e. g.,
in [11, 12].
We consider monadic logics on N with the relation “<”, that is, first-order logics where also
unary finite-value function variables and quantifiers over them are allowed. We also suppose that
we know some fixed finite-value function x : N → Σ and can use it in our formulas. Such a theory
is denoted by MT〈N, <, x〉 and is called monadic theory of x.
The main question here can be the question of decidability, that is, does there exist an algorithm
that given a sentence in a theory says whether this sentence is true of false.
The criterion of decidability for monadic theories of almost periodic sequences can be formulated
in terms of some their very natural characteristic, namely, almost periodicity regulator. An almost
periodicity regulator of an almost periodic sequence x is a function f : N → N such that every factor
u of x of length n occurs in each factor of x of length f(n). So an almost periodicity regulator
somehow regulates how periodic a sequence is. Notice that an almost periodicity regulator of a
sequence is not unique: every function greater than regulator is also a regulator.
Theorem 2 (Semenov 1983 [12]). If x is almost periodic, then MT〈N, <, x〉 is decidable iff x and
some its almost periodicity regulator are computable.
The following result was obtained recently, but uses the technics already used in [11, 12].
Theorem 3 (Carton, Thomas 2002 [2]). If x is morphic, then MT〈N, <, x〉 is decidable.
A curious result can be implied from two these theorems.
Corollary 4. If x is both morphic and almost periodic, then some its regulator is computable.
Proof. Indeed, if x is morphic, then by Theorem 3 the theory MT〈N, <, x〉 is decidable. Since
x is almost periodic, from Theorem 2 it follows that some almost periodicity regulator of x is
computable.
Notice that Corollary 4 does not imply the existence of an algorithm that given a morphic
sequence computes some almost periodicity regulator of this sequence whenever it is almost periodic
(but probably this algorithm can be constructed after deep analyzing the proofs of Theorems 2 and 3
and showing uniformity in a sense). And it also does not imply the decidability of almost periodicity
for morphic sequences. This decidability also does not imply Corollary 4.
By the way, Corollary 4 allows us to hope that these algorithms exist. Though the formulation
of this statement uses only combinatorics on words, the proof also involves the theory of monadic
logics. Of course, it would be interesting to find a simple combinatorial proof of the result.
And the last remark here is that Corollary 4 (and its probable uniform version) seems to be
the best progress that we can obtain by this monadic approach. One could try to express in the
monadic theory of morphic sequence (which is decidable by Theorem 3) the property of almost
periodicity, but it turns out to be impossible.
6 In General Case
We have described two polynomial-time algorithms, but without any precise bound for their working
time. Of course, it can be done after deep analyzing of all the previous, but is probably not so
interesting.
It is not still known whether the problem of determining almost periodicity of arbitrary morphic
sequence is decidable. Corollary 4 somehow supports the conjecture of decidability (but even does
not follow from this conjecture!).
Theorem 7.5.1 from [1] allows us to represent an arbitrary morphic sequence h(φ∞(s)) as
g(ψ∞(b)) where ψ is non-erasing. So it is sufficient to solve our main problem for h(φ∞(s)) with
non-erasing φ.
It seems that the general problem is tightly connected with a particular case of h(φ∞(a)) where
|φ(b)| > 2 for each b ∈ A. There is no strict reduction to this case but solving problem in this case
can help to deal with general situation.
The problem of finding an effective periodicity criterion in the case of arbitrary morphic se-
quences is also of great interest, as well as criteria for variations with periodicity and almost pe-
riodicity: ultimate periodicity, generalized almost periodicity, ultimate almost periodicity (see [9]
for definitions). If one notion is a particular case of another, it does not mean that corresponding
criterion for the first case is more difficult (or less difficult) than for the second.
Acknowledgements
The author is grateful to An. Muchnik and A. Semenov for their permanent help in the work, to
A. Frid, M. Raskin, K. Saari and to all the participants of Kolmogorov seminar, Moscow [4], for
fruitful discussions, and also to anonymous referees for very useful comments.
References
[1] J.-P. Allouche, J. Shallit. Automatic Sequences. Cambridge University Press, 2003.
[2] O. Carton, W. Thomas. The Monadic Theory of Morphic Infinite Words and Generalizations.
Information and Computation, vol. 176, pp. 51–76, 2002.
[3] A. Cobham. Uniform tag sequences. Math. Systems Theory, 6, pp. 164–192, 1972.
[4] Kolmogorov Seminar: http://lpcs.math.msu.su/kolmogorovseminar/eng/.
[5] A. Maes. More on morphisms and almost-periodicity. Theoretical Computer Science, vol. 231,
N 2, pp. 205–215, 2000.
[6] M. Morse, G. A. Hedlund. Symbolic dynamics. American Journal of Mathematics, 60, pp. 815–
866, 1938.
[7] An. Muchnik, A. Semenov, M. Ushakov. Almost periodic sequences. Theoretical Computer
Science, vol. 304, pp. 1–33, 2003.
[8] Yu. L. Pritykin. Finite-Automaton Transformations of Strictly Almost-Periodic Se-
quences. Mathematical Notes, vol. 80, N 5, pp. 710–714, 2006. Preprint on
http://arXiv.org/abs/cs.DM/0605026.
[9] Yu. Pritykin. Almost Periodicity, Finite Automata Mappings and Related Effectiveness Issues.
Proceedings of WoWA’06, St. Petersburg, Russia (satellite to CSR’06). To appear in ”Izvestia
VUZov. Mathematics”, 2007. Preprint on http://arXiv.org/abs/cs.DM/0607009.
[10] Yu. Pritykin. On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases.
Accepted to Developments in Language Theory, Turku, Finland, 2007. To appear in Lecture
Notes in Computer Science.
[11] A. L. Semenov. On certain extensions of the arithmetic of addition of natural numbers. Math.
of USSR, Izvestia, vol. 15, pp. 401–418, 1980.
[12] A. L. Semenov. Logical theories of one-place functions on the set of natural numbers. Math. of
USSR, Izvestia, vol. 22, pp. 587–618, 1983.
[13] Eric W. Weisstein. Bell Number. From MathWorld — A Wolfram Web Resource.
http://mathworld.wolfram.com/BellNumber.html
	Introduction
	Preliminaries
	Pure Morphic Sequences Generated by Non-erasing Morphisms
	Uniform Morphisms
	Equivalence Relations and Uniform Morphisms
	Criterion
	Polynomiality
	Monadic Theories
	In General Case

  In some particular cases we give criteria for morphic sequences to be almost
periodic (=uniformly recurrent). Namely, we deal with fixed points of
non-erasing morphisms and with automatic sequences. In both cases a
polynomial-time algorithm solving the problem is found. A result more or less
supporting the conjecture of decidability of the general problem is given.

Introduction
Different problems of decidability in combinatorics on words are always of great interest and dif-
ficulty. Here we deal with two main types of symbolic infinite sequences — morphic and almost
periodic — and try to understand connections between them. Namely, we are trying to find an
algorithmic criterion which given a morphic sequence decides whether it is almost periodic.
Though the main problem still remains open, we propose polynomial-time algorithms solving
the problem in two important particular cases: for pure morphic sequences generated by non-erasing
morphisms (Section 3) and for automatic sequences (Section 4). In Section 5 we say a few words
about connections with monadic logics. In particular, in a curious result of Corollary 4 we give a
reason why the main problem may be decidable.
Some attempts to solve the problem were already done. In [3] A. Cobham gives a criterion for
automatic sequence to be almost periodic. But even if his criterion gives some effective procedure
solving the problem (which is not clear from his result, and he does not care about it at all), this
procedure could not be fast. We construct a polynomial-time algorithm solving the problem. In [5]
A. Maes deals with pure morphic sequences and finds a criterion for them to belong to a slightly
different class of generalized almost periodic sequences (but he calls them almost periodic — see
[9] for different definitions). And again, his algorithm does not seem to be polynomial-time.
All the results of this paper can be found in [10].
2 Preliminaries
Denote the set of natural numbers {0, 1, 2, . . . } by N and the binary alphabet {0, 1} by B. Let A
be a finite alphabet. We deal with sequences over this alphabet, i. e., mappings x : N → A, and
denote the set of these sequences by AN.
∗Moscow State University, Russia, http://lpcs.math.msu.su/~pritykin/, yura@mccme.ru. The work was par-
tially supported by RFBR grants 06-01-00122, 05-01-02803, Kolmogorov grant of Institute of New Technologies, and
August Möbius grant of Independent University of Moscow.
http://arxiv.org/abs/0704.0218v1
Denote by A∗ the set of all finite words over A including the empty word Λ. If i ≤ j are natural,
denote by [i, j] the segment of N with ends in i and j, i. e., the set {i, i + 1, i + 2, . . . , j}. Also
denote by x[i, j] a subword x(i)x(i + 1) . . . x(j) of a sequence x. A segment [i, j] is an occurrence
of a word u ∈ A∗ in a sequence x if x[i, j] = u. We say that u 6= Λ is a factor of x if u occurs in x.
A word of the form x[0, i] for some i is called prefix of x, and respectively a sequence of the form
x(i)x(i+ 1)x(i+ 2) . . . for some i is called suffix of x and is denoted by x[i,∞). Denote by |u| the
length of a word u. The occurrence u = x[i, j] in x is k-aligned if k|i.
A sequence x is periodic if for some T we have x(i) = x(i+ T ) for each i ∈ N. This T is called
a period of x. We denote by P the class of all periodic sequences. Let us consider an extension of
this class.
A sequence x is called almost periodic1 if for every factor u of x there exists a number l such
that every factor of x of length l contains at least one occurrence of u (and therefore u occurs in x
infinitely many times). Obviously, to show almost periodicity of a sequence it is sufficient to check
the mentioned condition only for all prefixes but not for all factors (and even for some increasing
sequence of prefixes only). Denote by AP the class of all almost periodic sequences.
Let A, B be finite alphabets. A mapping φ : A∗ → B∗ is called a morphism if φ(uv) = φ(u)φ(v)
for all u, v ∈ A∗. A morphism is obviously determined by its values on single-letter words. A
morphism is non-erasing if |φ(a)| > 1 for each a ∈ A. A morphism is k-uniform if |φ(a)| = k for
each a ∈ A. A 1-uniform morphism is called a coding. For x ∈ AN denote
φ(x) = φ(x(0))φ(x(1))φ(x(2)) . . .
Further we consider only morphisms of the form A∗ → A∗ (but codings are of the form A → B,
which in fact does not matter, they can be also of the form A→ A without loss of generality). Let
φ(s) = su for some s ∈ A, u ∈ A∗. Then for all natural m < n the word φn(s) begins with the word
φm(s), so φ∞(s) = limn→∞ φ
n(s) = suφ(u)φ2(u)φ3(u) . . . is well-defined. If ∀n φn(u) 6= Λ, then
φ∞(s) is infinite. In this case we say that φ is prolongable on s. Sequences of the form h(φ∞(s))
for a coding h : A→ B are called morphic, of the form φ∞(a) are called pure morphic.
Notice that there exist almost periodic sequences that are not morphic (in fact, the set of almost
periodic sequences has cardinality continuum, while the set of morphic sequences is obviously
countable), as well as there exist morphic sequences that are not almost periodic (you will find
examples later). Our goal is to determine whether a morphic sequence is almost periodic or not
given its constructive definition.
First of all, observe the following
Lemma 1. A sequence φ∞(s) is almost periodic iff s occurs in this sequence infinitely many times
with bounded distances.
Proof. In one direction the statement is obviously true by definition.
Suppose now that s occurs in φ∞(s) infinitely many times with bounded distances. Then for
every m the word φm(s) also occurs in φ∞(s) infinitely many times with bounded distances. But
every word u occurring in φ∞(s) occurs in some prefix φm(s) and thus occurs infinitely many times
with bounded distances.
For a morphism φ : {1, . . . , n} → {1, . . . , n} we can define a corresponding matrix M(φ), such
that M(φ)ij is a number of occurrences of symbol i into φ(j). One can easily check that for each l
we have M(φ)l =M(φl).
Morphism φ is called primitive if for some l all the numbers in M(φl) are positive.
1It was called strongly or strictly almost periodic in [7, 8].
Let us construct an oriented graph G corresponding to a morphism. Let its set of vertices be
A. In G edges go from b ∈ A to all the symbols occurring in φ(b).
For φ∞(s) it can easily be found using the graph corresponding to φ which symbols from A
really occur in this sequence. Indeed, these symbols form the set of all vertices that can be reached
from s. So without loss of generality from now on we assume that all the symbols from A occur in
φ∞(s).
A morphism is primitive if and only if its corresponding graph is strongly connected, i. e., there
exists an oriented path between every two vertices. This reformulation of the primitiveness notion
seems to be more appropriate for computational needs.
By Lemma 1 (and the observation that codings preserve almost periodicity) morphic sequences
obtained by primitive morphisms are always almost periodic. Moreover, in the case of increasing
morphisms (such that |φ(b)| > 2 for each b) this sufficient condition is also necessary (and this
is a polynomial-time algorithmic criterion). However when we generalize this case even on non-
erasing morphisms, it is not enough to consider only the corresponding graph or even the matrix
of morphism (which has more information), as it can be seen from the following example.
Let φ1 be as follows: 0 → 01, 1 → 120, 2 → 2, and φ2 be as follows: 0 → 01, 1 → 210, 2 → 2.
Then these two morphisms have identical matrices of morphism, but φ∞1 (0) is almost periodic, while
φ∞2 (0) is not. Indeed, in φ
2 (0) there are arbitrary long segments like 222. . . 22, so φ
2 (0) /∈ AP .
There is no such problem in φ∞1 (0). Since 0 occurs in both φ1(0) and φ1(1), and 22 does not occur
in φ∞1 (0), it follows that 0 occurs in φ
1 (0) with bounded distances. Thus φ
1 (0) for every m > 0
occurs in φ∞1 (0) with bounded distances, so φ
1 (0) ∈ AP. See Theorem 1 for a general criterion of
almost periodicity in the case of fixed points of non-erasing morphisms.
To introduce a bit the notion of almost periodicity, let us formulate an interesting result on this
topic. It seems to be first proved in [3], but also follows from the results of [9]. For x ∈ AN, y ∈ BN
define x× y ∈ (A×B)N such that (x× y)(i) = 〈x(i), y(i)〉.
Proposition 1. If x is almost periodic and y is periodic, then x× y is almost periodic.
3 Pure Morphic Sequences Generated by Non-erasing Morphisms
Here we consider the case of morphic sequence of the form φ∞(s) for non-erasing φ. We present an
algorithm that determines whether a morphic sequence φ∞(s) is almost periodic given an alphabet
A, a morphism φ and a symbol s ∈ A.
Suppose we have A, φ and s ∈ A, such that |A| = n, maxb∈A |φ(b)| = k, s begins φ(s).
Remember that we suppose that all the symbols from A appear in φ∞(s).
Divide A into two parts. Let I be the set of all symbols b ∈ A such that |φm(b)| → ∞ as
m→ ∞. Denote F = A \ I, it is the set of all symbols b such that |φm(b)| is bounded. Also define
E ⊆ F to be the set of all symbols b such that |φ(b)| = 1.
We can find a decomposition A = I ⊔ F in poly(n, k)-time as follows.
Find E. Then find all the cycles in G with all the vertices lying in E. Join all the vertices of all
these cycles in a set D. This set is stabilizing: F is the set of all vertices in G such that all infinite
paths starting from them stabilize in D. Polynomiality can be checked easily.
Construct “a graph of left tails” L with marked edges. Its set of vertices is I. From each vertex
b exactly one edge goes off. To construct this edge, find a representation φ(b) = uv, where c ∈ I,
u is the maximal prefix of φ(b) containing only symbols from F . It follows from the definitions
of I and F that u does not coincide with φ(b), that is why this representation is correct. Then
construct in L an edge from b to c and write u on it.
Analogously we construct “a graph of right tails” R. (In this case we consider representations
φ(b) = vu where u ∈ F ∗, c ∈ I.)
Now we formulate a general criterion.
Theorem 1. A sequence φ∞(s) is almost periodic iff
1) G restricted to I is strongly connected;
2) in graphs L and R on each edge of each cycle an empty word Λ is written.
It seems that full and detailed proof of this theorem can only confuse a reader, rather than a
proof sketch.
Proof sketch. By Lemma 1 for almost periodicity it is necessary and sufficient to check whether
symbol s occurs infinitely many times with bounded distances.
For every symbol b ∈ I the symbol s should occur in some φl(b), that is what the 1st part of
the criterion says.
Furthermore, in the sequence φ∞(s) all the segments of consecutive symbols from F should be
bounded. Indeed, every such segment consists only of symbols from F , but s /∈ F . That is what
the 2nd part of the criterion means, let us explain why.
Consider some v = buc occurring somewhere in φ∞(a), where b, c ∈ I, u ∈ F ∗. Every element
of sequence of words v, φ(v), φ2(v), φ3(v), . . . occurs in φ∞(s). Somewhere in the middle of φl(v) =
φl(b)φl(u)φl(c) a word φl(u) occurs. As l increases, some words from F ∗ might stick to φl(u) from
left or right for these words can come from φl(b) or φl(c). These words exactly correspond to those
written on edges of L or R. The 2nd part of the criterion exactly says that this situation can
happen only finitely many times, until we get to some cycle in L or R.
Let us consider examples with φ1 and φ2 from the end of Section 2. In both cases I = {0, 1},
F = {2}. On every edge of R in both cases Λ is written. Almost the same is true for L: the only
difference is about the edge going from 1 to 1. In the case of φ1 an empty word is written on this
edge, while in the case of φ2 a word 2 is written. That is why φ
1 (0) is almost periodic, while φ
2 (0)
is not.
Corollary 1. If for all b ∈ A we have |φ(b)| > 2, then φ∞(s) is almost periodic iff φ is primitive.
Proof. Follows from Theorem 1. In that case A = I, and on all the edges of L and R the empty
word is written.
Corollary 2. There exists a poly(n, k)-algorithm that says whether φ∞(s) is almost periodic.
Proof. Conditions from Theorem 1 can be checked in polynomial time.
It also seems useful to formulate an explicit version of the criterion for the binary case. We do
it without any additional assumptions, opposite to the previous.
Corollary 3. For non-erasing φ : B → B that is prolongable on 0 a sequence φ∞(0) is almost
periodic iff one of the following conditions holds:
1) φ(0) contains only 0s;
2) φ(1) contains 0;
3) φ(1) = Λ;
4) φ(1) = 1 and φ(0) = 0u0 for some word u.
4 Uniform Morphisms
Now we deal with morphic sequences obtained by uniformmorphisms. Again we present a polynomial-
time algorithm for solving the problem in this situation.
Suppose we have an alphabet A, a morphism φ : A∗ → A∗, a coding h : A→ B, and s ∈ A, such
that |A| = n, |B| 6 n, ∀b ∈ A |φ(b)| = k, s begins φ(s). We are interested in whether h(φ∞(s)) is
almost periodic. Sequences of the form h(φ∞(s)) with φ being k-uniform are also called k-automatic
(see [1]).
4.1 Equivalence Relations and Uniform Morphisms
For each l ∈ N define an equivalence relation on A: b ∼l c iff h(φ
l(b)) = h(φl(b)). We can easily
continue this relation on A∗: u ∼l v iff h(φ
l(u)) = h(φl(v)). In fact, this means |u| = |v| and
u(i) ∼l v(i) for all i, 1 6 i 6 |u|.
Let Bm be the Bell number, i. e., the number of all possible equivalence relations on a finite
set with exactly m elements, see [13]. As it follows from this article, we can estimate Bm in the
following way.
Lemma 2. 2m 6 Bm 6 2
Cm logm for some constant C.
Thus the number of all possible relations ∼l is not greater than Bn = 2
O(n logn). Moreover, the
following lemma gives a simple description for the behavior of these relations as l tends to infinity.
Lemma 3. If ∼r equals ∼s, then ∼r+p equals ∼s+p for all p.
Proof. Indeed, suppose ∼r equals ∼s. Then b ∼r+1 c iff φ(b) ∼r φ(c) iff φ(b) ∼s φ(c) iff b ∼s+1 c.
So if ∼r equals ∼s, then ∼r+1 equals ∼s+1, which implies the lemma statement.
This lemma means that the sequence (∼l)l∈N turns out to be ultimately periodic with a period
and a preperiod both not greater than Bn. Thus we obtain the following
Lemma 4. For some p, q 6 Bn we have for all i and all t > p that ∼t equals ∼t+iq.
4.2 Criterion
Now we are trying to get a criterion which we could check in polynomial time. Notice that the
situation is much more difficult than in the pure case because of a coding allowed. In particular,
the analogue of Lemma 1 for non-pure case does not hold.
We will move step by step to the appropriate version of the criterion reformulating it several
times.
This proposition is quite obvious and follows directly from the definition of almost periodicity
since all h(φm(a)) are the prefixes of h(φ∞(a)).
Proposition 2. A sequence h(φ∞(s)) is almost periodic iff for all m the word h(φm(s)) occurs in
h(φ∞(s)) infinitely often with bounded distances.
And now a bit more complicated version.
Proposition 3. A sequence h(φ∞(s)) is almost periodic iff for all m the symbols that are ∼m-
equivalent to s occur in φ∞(s) infinitely often with bounded distances.
Proof. ⇐. If the distance between two consecutive occurrences in φ∞(s) of symbols that are ∼m-
equivalent to s is not greater than t, then the distance between two consecutive occurrences of
h(φm(s)) in h(φ∞(s)) is not greater than tkm.
⇒. Suppose h(φ∞(s)) is almost periodic. Let ym = 012 . . . (k
m − 2)(km − 1)01 . . . (km − 1)0 . . .
be a periodic sequence with a period km. Then by Proposition 1 a sequence h(φ∞(s))×ym is almost
periodic, which means that the distances between consecutive km-aligned occurrences of h(φm(s))
in h(φ∞(s)) are bounded. It only remains to notice that if h(φ∞(s))[ikm, (i+1)km−1] = h(φm(s)),
then φ∞(s)(i) ∼m s.
Let Ym be the following statement: symbols that are ∼m-equivalent to s occur in φ
∞(s) infinitely
often with bounded distances.
Suppose for some T that YT is true. This implies that h(φ
T (s)) occurs in h(φ∞(s)) with bounded
distances. Therefore for all m 6 T a word h(φm(s)) occurs in h(φ∞(s)) with bounded distances
since h(φm(s)) is a prefix of h(φT (s)). Thus we do not need to check the statements Ym for all m,
but only for all m > T for some T .
Furthermore, it follows from Lemma 4, that we are sufficient to check the only one such state-
ment as in the following
Proposition 4. For all r > Bn: a sequence h(φ
∞(s)) is almost periodic iff the symbols that are
∼r-equivalent to s occur in φ
∞(s) infinitely often with bounded distances.
And now the final version of our criterion.
Proposition 5. For all r > Bn: a sequence h(φ
∞(s)) is almost periodic iff for some m the symbols
that are ∼r-equivalent to s occur in φ
m(b) for all b ∈ A.
Indeed, if the symbols of some set occur with bounded distances, then they occur on each
km-aligned segment for some sufficiently large m.
4.3 Polynomiality
Now we explain how to check a condition from Proposition 5 in polynomial time. We need to
show two things: first, how to choose some r > Bn and to find in polynomial time the set of all
symbols that are ∼r-equivalent to s (and this is a complicated thing keeping in mind that Bn is
exponential), and second, how to check whether for some m the symbols from this set for all b ∈ A
occur in φm(b).
Let us start from the second. Suppose we have found the set H of all the symbols that are
∼r-equivalent to s. For m ∈ N let us denote by P
m the set of all the symbols that occur in
φm(b). Our aim is to check whether exists m such that for all b we have P
m ∩H 6= ∅. First of
all, notice that if ∀b P
m ∩H 6= ∅, then ∀b P
∩H 6= ∅ for all l > m. Second, notice that the
sequence of tuples of sets ((P
m )b∈Σ)
m=0 is ultimately periodic. Indeed, the sequence (P
m=0 is
obviously ultimately periodic with both period and preperiod not greater than 2n (recall that n is
the size of the alphabet Σ). Thus the period of ((P
m )b∈Σ)
m=0 is not greater than the least common
divisor of that for (P
m=0, b ∈ A, and the preperiod is not greater than the maximal that of
m=0. So the period is not greater than (2
n)n = 2n
and the preperiod is not greater than 2n.
Third, notice that there is a polynomial-time-procedure that given a graph corresponding to some
morphism ψ (see Section 2 to recall what is the graph corresponding to a morphism) outputs a
graph corresponding to morphism ψ2. Thus after repeating this procedure n2 + 1 times we obtain
a graph by which we can easily find (P
)b∈Σ, since 2
n2+1 > 2n
+ 2n.
Similar arguments, even described with more details, are used in deciding our next problem.
Here we present a polynomial-time algorithm that finds the set of all symbols that are ∼r-equivalent
to s for some r > Bn.
We recursively construct a series of graphs Ti. Let its common set of vertices be the set of all
unordered pairs (b, c) such that b, c ∈ A and b 6= c. Thus the number of vertices is
n(n−1)
. The set
of all vertices connected with (b, c) in the graph Ti we denote by Vi(b, c).
Define a graph T0. Let V0(b, c) be the set {(φ(b)(j), φ(c)(j)) | j = 1, . . . , k, φ(b)(j) 6= φ(c)(j)}.
In other words, b ∼l+1 c if and only if x ∼l y for all (x, y) ∈ V0(b, c).
Thus b ∼2 c if and only if for all (x, y) ∈ V0(b, c) for all (z, t) ∈ V0(x, y) we have z ∼0 t. For the
graph T1 let V1(b, c) be the set of all (x, y) such that there is a path of length 2 from (b, c) to (x, y)
in T0. The graph T1 has the following property: b ∼2 c if and only if x ∼0 y for all (x, y) ∈ V1(b, c).
And even more generally: b ∼l+2 c if and only if x ∼l y for all (x, y) ∈ V1(b, c).
Now we can repeat operation made with T0 to obtain T1. Namely, in T2 let V2(b, c) be the set of
all (x, y) such that there is a path of length 2 from (b, c) to (x, y) in T1. Then we obtain: b ∼l+4 c
if and only if x ∼l y for all (x, y) ∈ V2(b, c).
It follows from Lemma 2 that log2Bn 6 Cn logn. Thus after we repeat our procedure r =
[Cn log n] times, we will obtain the graph Tl such that b ∼2r c if and only if x ∼0 y for all
(x, y) ∈ V2(b, c). Recall that x ∼0 y means h(x) = h(y), so now we can easily compute the set of
symbols that are ∼2r -equivalent to s.
5 Monadic Theories
Combinatorics on words is closely connected with the theory of second order monadic logics. Here
we just want to show some examples of these connections. More details can be found, e. g.,
in [11, 12].
We consider monadic logics on N with the relation “<”, that is, first-order logics where also
unary finite-value function variables and quantifiers over them are allowed. We also suppose that
we know some fixed finite-value function x : N → Σ and can use it in our formulas. Such a theory
is denoted by MT〈N, <, x〉 and is called monadic theory of x.
The main question here can be the question of decidability, that is, does there exist an algorithm
that given a sentence in a theory says whether this sentence is true of false.
The criterion of decidability for monadic theories of almost periodic sequences can be formulated
in terms of some their very natural characteristic, namely, almost periodicity regulator. An almost
periodicity regulator of an almost periodic sequence x is a function f : N → N such that every factor
u of x of length n occurs in each factor of x of length f(n). So an almost periodicity regulator
somehow regulates how periodic a sequence is. Notice that an almost periodicity regulator of a
sequence is not unique: every function greater than regulator is also a regulator.
Theorem 2 (Semenov 1983 [12]). If x is almost periodic, then MT〈N, <, x〉 is decidable iff x and
some its almost periodicity regulator are computable.
The following result was obtained recently, but uses the technics already used in [11, 12].
Theorem 3 (Carton, Thomas 2002 [2]). If x is morphic, then MT〈N, <, x〉 is decidable.
A curious result can be implied from two these theorems.
Corollary 4. If x is both morphic and almost periodic, then some its regulator is computable.
Proof. Indeed, if x is morphic, then by Theorem 3 the theory MT〈N, <, x〉 is decidable. Since
x is almost periodic, from Theorem 2 it follows that some almost periodicity regulator of x is
computable.
Notice that Corollary 4 does not imply the existence of an algorithm that given a morphic
sequence computes some almost periodicity regulator of this sequence whenever it is almost periodic
(but probably this algorithm can be constructed after deep analyzing the proofs of Theorems 2 and 3
and showing uniformity in a sense). And it also does not imply the decidability of almost periodicity
for morphic sequences. This decidability also does not imply Corollary 4.
By the way, Corollary 4 allows us to hope that these algorithms exist. Though the formulation
of this statement uses only combinatorics on words, the proof also involves the theory of monadic
logics. Of course, it would be interesting to find a simple combinatorial proof of the result.
And the last remark here is that Corollary 4 (and its probable uniform version) seems to be
the best progress that we can obtain by this monadic approach. One could try to express in the
monadic theory of morphic sequence (which is decidable by Theorem 3) the property of almost
periodicity, but it turns out to be impossible.
6 In General Case
We have described two polynomial-time algorithms, but without any precise bound for their working
time. Of course, it can be done after deep analyzing of all the previous, but is probably not so
interesting.
It is not still known whether the problem of determining almost periodicity of arbitrary morphic
sequence is decidable. Corollary 4 somehow supports the conjecture of decidability (but even does
not follow from this conjecture!).
Theorem 7.5.1 from [1] allows us to represent an arbitrary morphic sequence h(φ∞(s)) as
g(ψ∞(b)) where ψ is non-erasing. So it is sufficient to solve our main problem for h(φ∞(s)) with
non-erasing φ.
It seems that the general problem is tightly connected with a particular case of h(φ∞(a)) where
|φ(b)| > 2 for each b ∈ A. There is no strict reduction to this case but solving problem in this case
can help to deal with general situation.
The problem of finding an effective periodicity criterion in the case of arbitrary morphic se-
quences is also of great interest, as well as criteria for variations with periodicity and almost pe-
riodicity: ultimate periodicity, generalized almost periodicity, ultimate almost periodicity (see [9]
for definitions). If one notion is a particular case of another, it does not mean that corresponding
criterion for the first case is more difficult (or less difficult) than for the second.
Acknowledgements
The author is grateful to An. Muchnik and A. Semenov for their permanent help in the work, to
A. Frid, M. Raskin, K. Saari and to all the participants of Kolmogorov seminar, Moscow [4], for
fruitful discussions, and also to anonymous referees for very useful comments.
References
[1] J.-P. Allouche, J. Shallit. Automatic Sequences. Cambridge University Press, 2003.
[2] O. Carton, W. Thomas. The Monadic Theory of Morphic Infinite Words and Generalizations.
Information and Computation, vol. 176, pp. 51–76, 2002.
[3] A. Cobham. Uniform tag sequences. Math. Systems Theory, 6, pp. 164–192, 1972.
[4] Kolmogorov Seminar: http://lpcs.math.msu.su/kolmogorovseminar/eng/.
[5] A. Maes. More on morphisms and almost-periodicity. Theoretical Computer Science, vol. 231,
N 2, pp. 205–215, 2000.
[6] M. Morse, G. A. Hedlund. Symbolic dynamics. American Journal of Mathematics, 60, pp. 815–
866, 1938.
[7] An. Muchnik, A. Semenov, M. Ushakov. Almost periodic sequences. Theoretical Computer
Science, vol. 304, pp. 1–33, 2003.
[8] Yu. L. Pritykin. Finite-Automaton Transformations of Strictly Almost-Periodic Se-
quences. Mathematical Notes, vol. 80, N 5, pp. 710–714, 2006. Preprint on
http://arXiv.org/abs/cs.DM/0605026.
[9] Yu. Pritykin. Almost Periodicity, Finite Automata Mappings and Related Effectiveness Issues.
Proceedings of WoWA’06, St. Petersburg, Russia (satellite to CSR’06). To appear in ”Izvestia
VUZov. Mathematics”, 2007. Preprint on http://arXiv.org/abs/cs.DM/0607009.
[10] Yu. Pritykin. On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases.
Accepted to Developments in Language Theory, Turku, Finland, 2007. To appear in Lecture
Notes in Computer Science.
[11] A. L. Semenov. On certain extensions of the arithmetic of addition of natural numbers. Math.
of USSR, Izvestia, vol. 15, pp. 401–418, 1980.
[12] A. L. Semenov. Logical theories of one-place functions on the set of natural numbers. Math. of
USSR, Izvestia, vol. 22, pp. 587–618, 1983.
[13] Eric W. Weisstein. Bell Number. From MathWorld — A Wolfram Web Resource.
http://mathworld.wolfram.com/BellNumber.html
	Introduction
	Preliminaries
	Pure Morphic Sequences Generated by Non-erasing Morphisms
	Uniform Morphisms
	Equivalence Relations and Uniform Morphisms
	Criterion
	Polynomiality
	Monadic Theories
	In General Case
