On two-sided infinite fixed points of morphisms
Let Sigma be a finite alphabet, and let h: Sigma* --> Sigma* be a morphism. Finite and infinite fixed points of morphisms-i.e., those words w such that h(w)=w-play 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. (C) 2002 Elsevier Science B.V. All rights reserved.
fixed point morphism combinatorics on words infinite words