## On two-sided infinite fixed points of morphisms.(English)Zbl 0945.68115

Ciobanu, Gabriel (ed.) et al., Fundamentals of computation theory. 12th international symposium, FCT ’99. Iaşi, Romania, August 30 - September 3, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1684, 488-499 (1999).
Summary: Let $$\Sigma$$ be a finite alphabet, and let $$h: \Sigma^*\to \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.
For the entire collection see [Zbl 0921.00033].

### MSC:

 68Q45 Formal languages and automata 68R15 Combinatorics on words

finite alphabet