A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the equivalence problem of context-free and DT0L languages
Tekijät: Honkala J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1999
Journal: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 98
Numero: 1-2
Aloitussivu: 147
Lopetussivu: 149
Sivujen määrä: 3
ISSN: 0166-218X
DOI: https://doi.org/10.1016/S0166-218X(99)00120-1
Tiivistelmä
It is undecidable whether or not a given context-free language and a propagating DT0L language are equal. We show that equivalence is decidable between context-free and everywhere growing DT0L languages. (C) 1999 Elsevier Science B.V. All rights reserved.
It is undecidable whether or not a given context-free language and a propagating DT0L language are equal. We show that equivalence is decidable between context-free and everywhere growing DT0L languages. (C) 1999 Elsevier Science B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali