On two-sided infinite fixed points of morphisms (Q5958325)

From MaRDI portal
scientific article; zbMATH DE number 1715326
Language Label Description Also known as
English
On two-sided infinite fixed points of morphisms
scientific article; zbMATH DE number 1715326

    Statements

    On two-sided infinite fixed points of morphisms (English)
    0 references
    0 references
    0 references
    3 March 2002
    0 references
    Let \(\Sigma\) be a finite alphabet, and let \(h:\Sigma^{*} \rightarrow \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.
    0 references
    morphism
    0 references
    fixed point
    0 references
    combinatorics on words
    0 references
    infinite words
    0 references

    Identifiers