The equality problem for infinite words generated by primitive morphisms

2009/04/15 by Juha Honkala, Honkala, Juha
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0904.2257

openalex publication_date 2009/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the equality problem for infinite words obtained by iterating morphisms. In particular, we give a practical algorithm to decide whether or not two words generated by primitive morphisms are equal.

Related

• A characterization of binary morphisms generating Lyndon infinite words
• Binary Morphisms to Ultimately Periodic Words
• Mapping words to powers by morphisms
• Infinite Words and Morphic Languages Formalized in Isabelle/HOL
• Morphisms generating antipalindromic words