A polynomial bound for certain cases of the DOL sequence equivalence problem



: Honkala J

Publisher: SPRINGER-VERLAG

: 2001

: Theory of Computing Systems

: THEORY OF COMPUTING SYSTEMS

: THEOR COMPUT SYST

: 34

: 3

: 263

: 272

: 10

: 1432-4350

DOI: https://doi.org/10.1007/s00224-001-0001-2


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.



Last updated on 2024-26-11 at 17:59