On the equivalence problem of context-free and DT0L languages



: Honkala J

Publisher: ELSEVIER SCIENCE BV

: 1999

: Discrete Applied Mathematics

: DISCRETE APPLIED MATHEMATICS

: DISCRETE APPL MATH

: 98

: 1-2

: 147

: 149

: 3

: 0166-218X

DOI: https://doi.org/10.1016/S0166-218X(99)00120-1


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.



Last updated on 2024-26-11 at 22:04