The ω sequence problem for DOL systems is decidable

Publisher Website
Google Scholar
Abstract
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.

This publication has 7 references indexed in Scilit: