A1 Refereed original research article in a scientific journal

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



Authors: Honkala J

Publisher: SPRINGER-VERLAG

Publication year: 2001

Journal: Theory of Computing Systems

Journal name in source: THEORY OF COMPUTING SYSTEMS

Journal acronym: THEOR COMPUT SYST

Volume: 34

Issue: 3

First page : 263

Last page: 272

Number of pages: 10

ISSN: 1432-4350

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


Abstract
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