Bounds for the D0L language equivalence problem

We have recently proved that there is a bound for the sequence equivalence problem of polynomially bounded D0L systems depending only on the cardinality of the underlying alphabet. In this paper we deduce a similar bound for the language equivalence problem of polynomially bounded D0L systems. More generally, we prove that if a given class of D0L systems (satisfying certain natural conditions) has a uniform bound for sequence equivalence then it also has a uniform bound for language equivalence.

Authors

• Juha Honkala

Keywords

• D0L systems
• Equivalence problem
• Decidability