On two-sided infinite fixed points of morphisms |
| |
Authors: | Jeffrey Shallit Ming-wei Wang |
| |
Affiliation: | Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 |
| |
Abstract: | Let Σ be a finite alphabet, and let h:Σ* → Σ* 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. |
| |
Keywords: | Morphism Fixed point Combinatorics on words Infinite words |
本文献已被 ScienceDirect 等数据库收录! |
|