A polynomial bound for certain cases of the DOL sequence equivalence problem - UTU Tutkimustietojärjestelmä

A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

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

Tekijät: Honkala J

Kustantaja: SPRINGER-VERLAG

Julkaisuvuosi: 2001

Journal: Theory of Computing Systems

Tietokannassa oleva lehden nimi: THEORY OF COMPUTING SYSTEMS

Lehden akronyymi: THEOR COMPUT SYST

Vuosikerta: 34

Numero: 3

Aloitussivu: 263

Lopetussivu: 272

Sivujen määrä: 10

ISSN: 1432-4350

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

Tiivistelmä

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.