The ω sequence problem for DOL systems is decidable
Karel Čulík, Tero Harju · Journal of the ACM · 1984
The following problem is shown to be decidable.Given are homomorphisms h~ and h2 from 2" to ~* and strings a~ and a2 over 2: such that h,~(a,) is a proper prefix of h?+~(o,) for t = 1, 2 and all n -> 0; that is, for t --1, 2, h, generates from o, an infinite string at with prefixes/g/(a~) for all n -> 0. Test whether at = a2.From this result easily follows the decidability of limit language equivalence (~-eqmvalence) for D0L systems.