×

On the subword equivalence problem for morphic words. (English) Zbl 0879.68064

Summary: 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 \(\omega\)-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 \(\omega\)-sequence equivalence problem to prove our result.
We prove that the subword equivalence problem is decidable for two morphic words, provided the morphisms are primitive and have bounded delays. We also prove that the subword equivalence problem is decidable for any pair of morphic words in the case of a binary alphabet.
Our results hold in fact for a stronger version, namely for the subword inclusion problem.

MSC:

68Q45 Formal languages and automata
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Berstel, J.; Séébold, P., A remark on morphic Sturmian words, RAIRO Inform. Theoret. Appl., 28, 225-263 (1994) · Zbl 0883.68104
[2] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[3] Čulik, K.; Fris, I., The decidability of the equivalence problem for DOL-systems, Inform. Control, 35, 20-39 (1977) · Zbl 0365.68074
[4] Čulik, K.; Harju, T., The \(ω\)-sequence equivalence problem for DOL systems is decidable, J. Assoc. Comput. Mach., 31, 282-298 (1984) · Zbl 0632.68078
[5] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., On binary equality sets and a solution to the test set conjecture in the binary case, J. Algebra, 85, 76-85 (1983) · Zbl 0523.68066
[6] Ehrenfeucht, A.; Rozenberg, G., Repetition of subwords in DOL languages, Inform. Control, 59, 13-35 (1983) · Zbl 0549.68076
[7] Harju, T.; Linna, M., On the periodicity of morphisms on free monoids, RAIRO Inform. Theoret. Appl., 20, 47-54 (1986) · Zbl 0608.68065
[8] Mossé, B., Puissance de mots et reconnaissabilité des points fixes d’une substitution, Theoret. Comput. Sci., 99, 327-334 (1992) · Zbl 0763.68049
[9] Pansiot, J., Decidability of periodicity for infinite words, RAIRO Inform. Theoret. Appl., 20, 43-46 (1986) · Zbl 0617.68063
[10] Queffelec, M., Substitution Dynamical Systems-Spectral Analysis, (Lecture Notes in Math., Vol. 1294 (1987), Springer: Springer Berlin) · Zbl 0642.28013
[11] Salomaa, A., Jewels of Formal Language Theory (1981), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0487.68063
[12] Séébold, P., An effective solution to the DOL periodicity problem in the binary case, EATCS Bull., 36, 137-151 (1988) · Zbl 0678.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.