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.


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