A1 Refereed original research article in a scientific journal
Bounds for the D0L language equivalence problem
Authors: Honkala J
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2004
Journal: Information and Computation
Journal name in source: INFORMATION AND COMPUTATION
Journal acronym: INFORM COMPUT
Volume: 190
Issue: 1
First page : 70
Last page: 80
Number of pages: 11
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2003.12.002
Abstract
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.
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.
UTU Research Portal