On two-sided infinite fixed points of morphisms.
Let &Sgr; be a finite alphabet, and let h:&Sgr;*&Sgr; be a morphism. Finite and infinite fixed points of morphismsi.e., those words w such that h(w)=wplay an important role in formal language theory. Head characterized the finite fixed points of h, and later, Head and Lando characterized the one-sided infinite fixed points of h. Our paper has two main results. First, we complete the characterization of fixed points of morphisms by describing all two-sided infinite fixed points of h, for both the "pointed" and "unpointed" cases. Second, we completely characterize the solutions to the equation h(xy)=yx in finite words.
called the Thue-Morse infinite word, is the unique one-sided infinite fixed point of  which
starts with 0. In fact, nearly every explicit construction of an infinite word avoiding certain
patterns involves the fixed point of a morphism; for example, see [8, 15, 24, 20]. One-sided
infinite fixed points of uniform morphisms also play a crucial role in the theory of automatic
sequences; see, for example, [1].
Because of their importance in formal languages, it is of great interest to characterize
all the fixed points, both finite and infinite, of a morphism h. This problem was first
studied by Head [9], who characterized the finite fixed points of h. Later, Head and Lando
[10] characterized the one-sided infinite fixed points of h. (For different proofs of these
characterizations, see Hamm and Shallit [7].) In this paper we complete the description
of all fixed points of morphisms by characterizing the two-sided infinite fixed points of h.
Related work was done by Lando [14]. Two-sided infinite words (sometimes called bi-infinite
words or bi-infinite sequences) play an important role in symbolic dynamics [16], and have
also been studied in automata theory [18, 19], cellular automata [12], and the theory of codes
[22, 5].
We first introduce some notation, some of which is standard and can be found in [11].
For single letters, that is, elements of \Sigma, we use the lower case letters a; b; c; d. For finite
words, we use the lower case letters t; u; v; w; x; z. For infinite words, we use bold-face
letters t; u; v; w;x;y; z. We let ffl denote the empty word. If w 2 \Sigma   , then by jwj we mean
the length of, or number of symbols in w. If S is a set, then by Card S we mean the number
of elements of S. We say x is a subword of y 2 \Sigma   if there exist words w; z 2 \Sigma   such
that
If h is a morphism, then we let h j denote the j-fold composition of h with itself. If there
exists an integer j  1 such that h j (a) = ffl, then the letter a is said to be mortal; otherwise
a is immortal. The set of mortal letters associated with a morphism h is denoted by M h .
The mortality exponent of a morphism h is defined to be the least integer t  0 such that
We write the mortality exponent as t. It is easy to prove
that exp(h)  Card M h .
We let \Sigma ! denote the set of all one-sided right-infinite words over the alphabet \Sigma. Most
of the definitions above extend to \Sigma ! in the obvious way. For example, if
then is a language, then we define
Perhaps slightly less obviously, we can also define a limiting word
for a letter a, provided
h . In this case, there exists t  0 such that
ffl. Then we define
which is infinite if and only if x 62 M
h . Note that the factorization of h(a) as wax, with
h and x 62 M
h , if it exists, is unique.
In a similar way, we let ! \Sigma denote the set of all left-infinite words, which are of the form
to be the set of
left-infinite words formed by concatenating infinitely many words from L, that is,
h , then we define the left-infinite word
Again, if the factorization of h(a) as wax exists, with w 62 M
then it is unique.
We can convert left-infinite to right-infinite words (and vice versa) using the reverse
operation, which is denoted w R . For example, if
We now turn to the notation for two-sided infinite words. These have been much less
studied in the literature than one-sided words, and the notation has not been standardized.
Some authors consider 2 two-sided infinite words to be identical if they agree after applying
a finite shift to one of the words. Other authors do not. (This distinction is sometimes
called vs. "pointed" [2, 17].) In this paper, we consider both the pointed and
unpointed versions of the equation As it turns out, the "pointed" version of
this equation is quite easy to solve, based on known results, while the "unpointed" case is
significantly more difficult. The latter is our first main result, which appears as Theorem 5.
We let \Sigma Z denote the set of all two-sided infinite words over the alphabet \Sigma, which are
of the form \Delta In displaying an infinite word as a concatenation of words,
we use a decimal point to the left of the character c 1 , to indicate how the word is indexed.
Of course, the decimal point is not part of the word itself. We define the shift oe(w) to be
the two-sided infinite word obtained by shifting w to the left one position, so that
Similarly, for k 2 Zwe define
If w;x are 2 two-sided infinite words, and there exists an integer k such that
we call w and x conjugates, and we write w  x. It is easy to see that  is an equivalence
relation. We extend this notation to languages as follows: if L is a set of two-sided infinite
words, then by w  L we mean there exists x 2 L such that w  x.
If w is a nonempty finite word, then by w Z we mean the two-sided infinite word
Using concatenation, we can join a left-infinite word with a right-infinite
word to form a new two-sided infinite word, as follows:
If L ' \Sigma   is a set of words, then we define
is a morphism, then we define
Finally, if
h , then we define
a two-sided infinite word. Note that in this case the factorization of h(a) as wax is not
necessarily unique, and we use the superscript i to indicate which a is being chosen.
We can produce one-sided infinite words from two-sided infinite words by ignoring the
portion to the right or left of the decimal point. Suppose We
define
a left-infinite word, and
a right-infinite word.
Finite and one-sided infinite fixed points
In this section we recall the results of Head [9] and Head and Lando [10]. We assume
is a morphism that is extended to the domains \Sigma ! and ! \Sigma in the manner
discussed above.
such that xay and xy 2 M
and
Note that there is at most one way to write h(a) in the form xay with xy 2 M
h .
Theorem 1 A finite word w 2 \Sigma   has the property that
h .
Theorem 2 The right-infinite word w is a fixed point of h if and only if at least one of the
following two conditions holds:
(a) w
(a) for some a 2 \Sigma, and there exist x 2 M
h and y 62 M
h such that
There is also an evident analogue of Theorem 2 for left-infinite words:
Theorem 3 The left-infinite word w is a fixed point of h if and only if at least one of the
following two conditions holds:
(a)
h for some a 2 \Sigma, and there exist x 62 M
h and y 2 M
h such that
3 Two-sided infinite fixed points: the "pointed" case
We assume h : \Sigma   ! \Sigma   is a morphism that is extended to the domain \Sigma Z in the manner
discussed above. In this section, we consider the equation
words.
Proposition 4 The equation solution if and only if at least one of the
following conditions holds:
(a) w 2 F Z
h for some a 2 \Sigma, and there exist x 62 M
h such that
or
(c)
(a) for some a 2 \Sigma, and there exist x 2 M
h such that
there exist x; z 62 M
h , such
that xay and
Proof. Let By definition, we have
so if
We may now apply Theorem 2 (resp., Theorem 3) to R(w) (resp., L(w)). There are 2
cases to consider for each side, giving 2 cases.
Example. Let  be the Thue-Morse morphism, which maps
the one-sided Thue-Morse
infinite word. Then there are exactly 4 two-sided infinite fixed points of g, as follows:
All of these fall under case (d) of Proposition 4. Incidentally, all four of these words are
overlap-free.
4 Two-sided infinite fixed points: the "unpointed" case
We assume h : \Sigma   ! \Sigma   is a morphism that is extended to the domain \Sigma Z in the manner
discussed above. In this section, we characterize the two-sided infinite fixed points of a
morphism in the "unpointed" case. That is, our goal is to characterize the solutions to
h(w)  w. The following theorem is the first of our two main results.
Theorem 5 Let h be a morphism. Then the two-sided infinite word w satisfies the relation
only if at least one of the following conditions holds:
(a) w  F Z
(b) w
h for some a 2 \Sigma, and there exist x 62 M
h and y 2 M
h such that
(c)
(a) for some a 2 \Sigma, and there exist x 2 M
h and y 62 M
h such that
(d) w
there exist x; z 62 M
h , such
that xay and
h !;i (a) for some a 2 \Sigma, and there exist x; y 62 M
h such that xay with
such that
Before we begin the proof of Theorem 5, we state and prove three useful lemmas.
Lemma 6 Suppose w, x are 2 two-sided infinite words with w  x. Then h(w)  h(x).
Proof. Since w  x, there exists j such that
0:
(2)
Our second lemma concerns periodicity of infinite words. We say a two-sided infinite
word
is periodic if there exists a nonempty word x such that there exists an integer
(w). The integer p is called a period of w.
Lemma 7 Suppose word such that there
exists a one-sided right-infinite word x and infinitely many negative indices 0 ?
such that
for j  1. Then w is periodic.
Proof. By assumption
for j  1. Hence c i j and so the right-infinite word x is periodic
of period . Since this is true for all j  1, it follows that x is periodic of period
so w is periodic of period g.
Our third lemma concerns the growth functions of iterated morphisms.
be a morphism. Then
(a) there exist integers
(b) there exists an integer M depending only on Card \Sigma such that for all
we have j  M .
We note that part (a) was asserted without proof by Cobham [4]. However, the proof
easily follows from a result of Dickson [6] that N k contains no infinite antichains under the
usual partial ordering; see also Konig [13]. For completeness, we give the following proof,
suggested by S. Astels (personal communication).
Proof. (a) Suppose g. First, choose i 1;1 to be the least index
such that jh i 1;1 (a 1 successively choose i
g.
choose i 2;1 to be the least index i
successively choose i
1. g.
Note that S 2 ' S 1 .
Continuing in this fashion, we produce an infinite sequence of indices
that jh i r;n (a j )j  jh i r;n+1 (a j )j for r and all n  1. We can then choose
(b) We omit the proof, although we observe that we can take
Now we can prove Theorem 5.
Proof. ((=): Suppose case (a) holds, and w  F Z
h . Then there exists x 2 F Z
h with
h , we can write
It follows that applying
Lemma 6, we conclude that h(w)
Next, suppose case (b) holds, and w
h . Then w  x for some x of the form
xay with x 62 M
h and y 2 M
h . Then we have
and by Lemma 6, we conclude that h(w)
Cases (c), (d), and (e) are similar to case (b).
Finally, if case (f) holds, then
and so
there exists k such that
Let
Then it is not hard to see that
Figure 1. Note that
c (1)
s
(0)+1
s
c .
s
c
c s (-1)+1
h(

Figure

1: Interpretation of the function s
We define the set C as follows: Our argument is divided into
two major cases, depending on whether or not C is empty.
Case 1: C 6= ;. In this case, there exists j such that j. Now consider the pointed
word We have x  w and by Eq. (4) we have
Then, by Proposition 4, one of cases (a)-(d) must hold.
Case 2: There are several subcases to consider.
Case 2a: There exist integers
Among all pairs (i; choose one with there exists
an integer k with is a pair satisfying (5) with smaller
difference, while if k ! j, then (k; j) is a pair satisfying (5) with smaller difference. Hence
k. But this is impossible by our assumption. It follows that
but 1). Hence this case cannot occur.
Case 2b: There exists an integer r such that s(i) ! i for all
all i  r. Then h(c r which by the inequalities contains c as a
subword. Therefore, letting a = c r , it follows that
where is a left-infinite word,
are finite words, and is a right-infinite word. Furthermore, we have
Now the equation implies that h(y) is a prefix of v, and by an easy induction
we have h(y)h 2 (y)h 3 (y) \Delta \Delta \Delta is a prefix of v. Suppose this prefix is finite. Then y
h , and
so
a contradiction, since we have assumed It follows
that z := h(y)h 2 (y)h 3 (y) \Delta \Delta \Delta is right-infinite and hence y 62 M
h .
By exactly the same reasoning, we find that \Delta \Delta \Delta h 3 (x) h 2 (x) h(x) is a left-infinite suffix of
u. We conclude that w
h !;i (a), and hence case (e) holds.
Case
Now consider the following factorization of certain conjugates of w, as follows: for i  0,
we have w  x i
word), and z right-infinite word). Note that
assumption, so i  s(i \Gamma 1); hence y i is nonempty. Evidently we have
Now the equation h(y i z implies that h(y i ) is a prefix of z i . Now an easy induction,
as in Case 2b, shows that v := h(y is a prefix of z i . If v were finite, then
we would have y
h , and so
Hence v is right-infinite, and so y
h . There are now two further subcases to consider:
Case 2ci: Suppose sup i0 It then follows that jy i j  d. Hence
there is a finite word u such that y infinitely many indices i  0. From the above
argument we see that the right-infinite word h(u)h 2 (u)h 3 (u) \Delta \Delta \Delta is a suffix of w, beginning
at position s(i for infinitely many indices i  0. We now use Lemma 7 to conclude
that w is periodic.
Thus we can write
loss of generality, we may assume p is minimal

We claim p. For if not we must have and then since
h(w)  w, we would have w is periodic with periods p and q, hence periodic of period
q). But since p was minimal we must have Hence q  2p. Now let
must have l ? 0. Then
It now follows that
for all integers i. Now multiplying
by \Gammal, we get \Gammalp ? l \Gammal in Eq. (7), and we have
a contradiction, since s(i) ? i for all i. It follows that
There exists k such that h(c 1 . Using the division theorem,
We have
By above we know jvj  1, so xy 6= ffl. Suppose
h . It
follows that w 2 F Z
h . A similar argument applies if
a contradiction. Thus x; y 6= ffl, and case (f) holds.
Case 2cii: sup i0
z
denotes the j-fold composition of the function
s with itself. First we prove the following technical lemma.
Lemma 9 For all integers r  1 there exists an integer n  0 such that B j (n) ? r for
t.
Proof. By induction on t. For the result follows since
sup
Now assume the result is true for t; we prove it for t + 1. Define m := max a2\Sigma jh(a)j. By
induction there exists an integer n 1 such that t. Then, by
the definition of m there exist an integer m, and an integer n 3 such
that s(n 3
Now
Similarly, we have
for all j  0. By the same reasoning, we have
for all j  0. Thus we find
(by Eq. (8))
(by induction and Eq. (9))
Similarly, for 2
r:
It thus follows that we can take This completes the proof of Lemma 9.
Now let M be the integer specified in Lemma 8, and define r := sup 1iM B i (0). By
Lemma 9 there exists an integer n  0 such that B
We have
It follows that
. But this contradicts Lemma 8. This contradiction shows that this case
cannot occur.
Case 2d: This case is the mirror image of Case 2c 1 , and the proof
is identical. The proof of Theorem 5 is complete.
5 Some examples
In this section we consider some examples of Theorem 5.
Example 1. Consider the morphism f defined by a
Then
This falls under case (f) of Theorem 5.
Example 2. Consider the morphism ' defined by 0
we have '(w)  w. This falls under case (e) of Theorem 5. Incidentally, c i equals the sum
of the digits, modulo 3, in the balanced ternary representation of i.
6 The equation in finite words
It is not difficult to see that it is decidable whether any of conditions (a)-(e) of Theorem 5
hold for a given morphism h. However, this is somewhat less obvious for condition (f) of
Theorem 5, which demands that the equation possess a nontrivial 2 solution. We
conclude this paper by discussing the solvability of this equation and, in our second main
result, we give a characterization of the solution set.
To do so it is useful to extend the notation , previously used for two-sided infinite
words, to finite words. We say w  z for w; z 2 \Sigma   if w is a cyclic shift of z, i.e., if there exist
such that It is now easy to verify that  is an equivalence
relation. Furthermore, if w  z, and h is a morphism, then h(w)  h(z). Thus condition
(f) can be restated as h(z)  z. The following theorem shows that the solvability of the
equation
1 Note that s(i) ? i for all i implies that hence Case 2d
really is the mirror image of Case 2c.
By nontrivial we mean xy 6= ffl.
Theorem 10 Let h be a morphism h : \Sigma   ! \Sigma   . Then h(z)  z possesses a solution z
if and only if F h d is nonempty for some 1  d  Card \Sigma.
Proof. (=: Suppose F h d is nonempty for some d, say x d. Then by definition of F h d,
xy. Then
and so there exist 0
such that h i In other words, h i (z) is a finite fixed point of h j \Gammai . Hence F h j\Gammai
is nonempty. This implies A h d is nonempty for some d with 1  d  Card \Sigma. Thus F h d is
nonempty.
Remarks.
1. Note that Theorem 10 does not characterize all the finite solutions of h(z)  z; it
simply gives a necessary and sufficient condition for solutions to exist.
2. As we have seen in Theorem 1, the set of finite solutions to z is finitely
generated, in that the solution set can be written as S   for some finite set T . However,
the set of solutions to h(z)  z need not even be context-free. For consider the morphism
defined by h(a)
If T were context-free, then so would be T " a
c
. But
c
which is not context-free.
We finish with a discussion of the set T of words z for which h(z)  z. From the proof
of Theorem 10, there exist i ! j such that h i (z) is a fixed point of h j \Gammai . Since h i (z)  z,
we may restrict our attention to the set
then is the set of all
cyclic permutations of words in S.
To describe S we introduce an auxiliary morphism ~ h : ~
\Sigma, where ~
a 2 ~
\Sigma if and only if the following three conditions hold:
(1) a is an immortal letter of h;
contains exactly one immortal letter for all i  1; and
contains a for some i  1.
We define the morphism ~
h by ~ h(a) = a 0 where a 0 is the unique immortal letter in h(a).
The relation of ~ h to S is as follows. If z 2 S, then z 2 F
Hence there exists
an integer p such that is an immortal letter
for 1  j  p. It follows easily that a j 2 ~
\Sigma. Hence h cyclically shifts z iff ~ h cyclically shifts
~
. (The words x j and y j are uniquely specified by i and a j .)
Theorem 11 We have
Card
Proof. Suppose a 2 ~
\Sigma. Define a j , x j and y j by a
where a j+1 2 ~
\Sigma. It is clear that there is a t  Card ~
\Sigma such that if j j k (mod t) then
By the definition of F h i , all words in F h i
are of the form
a e i
for some a = a 0 2 ~
\Sigma. Since there are only finitely many a j , x j and y j and e i  Card ~
\Sigma for
all i  1, the result follows.
Therefore, we now concentrate on the set ~
T of words ~ z that are cyclically shifted by ~ h.
Suppose ~
g. Since ~ h acts as a permutation P on ~
there exists a unique
factorization of P into disjoint cycles. Suppose appearing in the
factorization of P , and let jcj denote the length t of the cycle c. Define the language L(c) as
follows:
For example, if . Note that the definition
of L(c) is independent of the particular representation chosen for the cycle.
Now define the finite collection R 0 of regular languages as follows:
is a cycle of P and 1  v  jcj and gcd(v;
We now define a finite collection R of regular languages. Each language in R is the
union of some languages of R 0 . The union is defined as follows. Each language L(c v ) in R 0
is associated with a pair (t; v) where is an integer relatively prime to t. Then
the languages L(c v 1
are each a subset of the same language of R if and
only if the system of congruences
. (10)
possesses an integer solution x, where t m. Note that a language in R 0
may be a subset of several languages of R.
We say a word w is the perfect shuffle of words w and the first
j symbols of w are the first symbols of w in that order, the second j symbols of w are
the second symbols of w in that order, and so on. We write
The following theorem characterizes the set ~
T , and is our second main result.
Theorem 12 Let ~ z 2 ~
\Sigma   , and let ~ h permute ~
\Sigma. Then ~ h(~z)  ~ z if and only if ~
z is the perfect
shuffle of some finite number of words contained in some single language of R.
Proof. Let ~ h permute ~
\Sigma, with induced permutation P . Let ~
z is the perfect shuffle of some finite number of words contained in a single
language of R. For simplicity of notation we consider the case where ~
z is the perfect shuffle
of two such words; the general case is similar and is left to the reader.
Thus assume ~
w). Further, assume w 2 L(c v ) for some cycle c and integer v
relatively prime to
relatively prime to
t. (Here the indices are assumed to be taken modulo t.)
d s+1 for
t. (Here the indices are assumed to be taken modulo "
t.)
By hypothesis there exists an integer x such that vx j 1 (mod
t).
A simple calculation shows that we may assume 0  x
~
(indices of a taken mod n), and so ~ h(~z)  ~
z.
Suppose ~ h(~z)  ~
z. Then there exists an integer y such that ~ h(b
the indices are taken modulo n. Define
Then, considering its action on b 0 the morphism ~ h induces a permutation of the
indices n) which, by elementary group theory, factors
into g disjoint cycles, each of length m.
define the words
It is clear that ~
and so it follows that ~ h cyclically shifts each w i by y=g.
Now each k there is a unique solution t (mod m) of the congruence
y
Multiplying through by g, we find
has a solution t, so
has a solution t. But ~ h t (b so each symbol b kg+i of w i is in the orbit of ~
h on z i . It
follows that each symbol of w i is contained in the same cycle c i of P . Suppose c i has length
is the least positive integer with this property.
However, we also have ~ h m (b
there is a solution v to the congruence v \Delta y
m). Then
n). Using the division theorem, write
g. Since gcd(v; m) = 1, and t i j m, we must have
Now
Then for we have
From ~ h(b
and so y
Thus the system of equations (10) possesses a solution
This completes the proof.



--R

Automates finis en th'eorie des nombres.
Ensembles reconnaissables de mots bi-infinis
Axel Thue's Papers on Repetitions in Words: a Translation.
On the Hartmanis-Stearns problem for a class of tag machines
Finitary codes for biinfinite words.
Finiteness of the odd perfect and primitive abundant numbers with distinct factors.
Characterization of finite and one-sided infinite fixed points of morphisms on free monoids
On sequences which contain no repetitions.
Fixed languages and the adult languages of 0L schemes.
Fixed and stationary
Introduction to Automata Theory
Recursive cellular automata invariant sets.
Theorie der endlichen und unendlichen Graphen: kombinatorische Topologie der Streckenkomplexe.
Periodicity and ultimate periodicity of D0L systems.
A problem on strings of beads.
An Introduction to Symbolic Dynamics and Coding.
The limit set of recognizable substitution systems.
Ensembles reconnaissables de mots biinfinis.
Ensembles reconnaissables de mots biinfinis.



An inequality for non-negative matrices
--TR
Periodicity and ultimate periodicity of DOL systems
An introduction to symbolic dynamics and coding
Introduction To Automata Theory, Languages, And Computation
Ensembles reconnaissables de mots bi -infinis limite et dMYAMPERSANDeacute;terminisme
The Limit Set of Recognizable Substitution Systems
Ensembles reconnaissables de mots biinfinis

--CTR
F. Lev , G. Richomme, On a conjecture about finite fixed points of morphisms, Theoretical Computer Science, v.339 n.1, p.103-128, 11 June 2005
fixed point;combinatorics on words;morphism;infinite words