The decidability of the DOL-DTOL equivalence problem

摘要

It is shown that it is decidable of any endomorphisms σ, σ1…, σm and any words P, P1…, Pn whether or not σ∗(P) = {σ1,…,σm}∗ ({P1,…Pn}). As a consequence it is decidable of any endomorphisms σ1,…, σm and any words P1,…, Pn whether or not there exist an endomorphism σ and a word P such that the above equality holds true. In the positive case all such endomorphisms σ and words P can be effectively listed.