The ω-sequence equivalence problem for DOL systems is decidable
Karel Čulík, Tero Harju · 1981
The following problem is shown to be decidable. Given are homomorphisms h1 and h2 from Σ* to Σ* and strings σ1 and σ2 over Σ such that hni(σi) is a proper prefix of hn+1i (σi) for i = 1, 2 and all n ≥ 0, i.e. for i = 1, 2, hi generates from σi an infinite string αi with prefixes hni(σi) for all n ≥ 0. Test whether α1 = α2. From this result easily follows the decidability of limit language equivalence (ω-equivalence) for DOL systems.