A1 Journal article – refereed
On the equivalence problem of context-free and DT0L languages




List of Authors: Honkala J
Publisher: ELSEVIER SCIENCE BV
Publication year: 1999
Journal: Discrete Applied Mathematics
Journal name in source: DISCRETE APPLIED MATHEMATICS
Journal acronym: DISCRETE APPL MATH
Volume number: 98
Issue number: 1-2
Number of pages: 3
ISSN: 0166-218X

Abstract
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.


Internal Authors/Editors

Last updated on 2019-20-07 at 03:43