Bounds for the D0L language equivalence problem
We have recently proved that there is a bound for the sequence equivalence problem of polynomially bounded DOL 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 DOL systems. More generally, we prove that if a given class of DOL systems (satisfying certain natural conditions) has a uniform bound for sequence equivalence then it also has a uniform bound for language equivalence. (C) 2003 Elsevier Inc. All rights reserved.
equivalence problem d0l systems decidability