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

Shallit, Jeffrey; Wang, Ming-wei

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

Keywords:

finite alphabet