## The $$\omega$$-sequence equivalence problem for D0L systems is decidable.(English)Zbl 0632.68078

The following problem is shown to be decidable. Given are homomorphisms $$h_ 1$$ and $$h_ 2$$ from $$\Sigma^*$$ to $$\Sigma^*$$ and strings $$\sigma_ 1$$ and $$\sigma_ 2$$ over $$\Sigma$$ such that $$h^ n_ i(\sigma_ i)$$ is a proper prefix of $$h_ i^{n+1}(\sigma_ i)$$ for $$i=1,2$$ and all $$n\geq 0$$; that is, for $$i=1,2$$, $$h_ i$$ generates from $$\sigma_ i$$ an infinite string $$\alpha_ i$$ with prefixes $$h^ n_ i(\sigma_ i)$$ for all $$n\geq 0$$. Test whether $$\alpha_ 1=\alpha_ 2$$. From this result easily follows the decidability of limit language equivalence ($$\omega$$-equivalence) for D0L systems.

### MSC:

 68Q45 Formal languages and automata 68Q42 Grammars and rewriting systems
Full Text: