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

Authors
Honkala, J
Citation
J. Honkala, A polynomial bound for certain cases of the DOL sequence equivalence problem, THEOR C SYS, 34(3), 2001, pp. 263-272
Citations number
13
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORY OF COMPUTING SYSTEMS
ISSN journal
14324350 → ACNP
Volume
34
Issue
3
Year of publication
2001
Pages
263 - 272
Database
ISI
SICI code
1432-4350(200105/06)34:3<263:APBFCC>2.0.ZU;2-X
Abstract
All known bounds for the D0L sequence equivalence problem in the general ca se 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 si ze of the systems.