On the subword equivalence problem for morphic words Original Research Article

Two infinite words x and y are said to be subword equivalent if they have the same set of finite subwords (factors). The subword equivalence problem is the question whether two infinite words are subword equivalent. We show that, under mild hypotheses, the decidability of the subword equivalence problem implies the decidability of the ω-sequence equivalence problem, a problem which has been shown to be decidable by Čulik and Harju for morphic words (i.e. words generated by iterating a morphism). Yet, we do use the decidability of the ω-sequence equivalence problem to prove our result.