Bounds for the D0L language equivalence problem



: Honkala J

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2004

: Information and Computation

: INFORMATION AND COMPUTATION

: INFORM COMPUT

: 190

: 1

: 70

: 80

: 11

: 0890-5401

DOI: https://doi.org/10.1016/j.ic.2003.12.002


We have recently proved that there is a bound for the sequence equivalence problem of polynomially bounded DOL systems depending only on the cardinality of the underlying alphabet. In this paper we deduce a similar bound for the language equivalence problem of polynomially bounded DOL systems. More generally, we prove that if a given class of DOL systems (satisfying certain natural conditions) has a uniform bound for sequence equivalence then it also has a uniform bound for language equivalence. (C) 2003 Elsevier Inc. All rights reserved.



Last updated on 2024-26-11 at 14:39