A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Bounds for the D0L language equivalence problem
Tekijät: Honkala J
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2004
Journal: Information and Computation
Tietokannassa oleva lehden nimi: INFORMATION AND COMPUTATION
Lehden akronyymi: INFORM COMPUT
Vuosikerta: 190
Numero: 1
Aloitussivu: 70
Lopetussivu: 80
Sivujen määrä: 11
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2003.12.002
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali