A polynomial bound for certain cases of the D0L sequence equivalence problem. (English) Zbl 0988.68106
Summary: All known bounds for the D0L sequence equivalence problem in the general case are huge. We give a bound for polynomially bounded PD0L systems which is less than cubic with respect to the cardinality of the alphabet and the size of the systems.
MSC:
68Q45 | Formal languages and automata |