Journal article
On strongly context-free languages
Abstract
We investigate the context-free languages whose complements are also context-free. We call them strongly context-free languages. The family of strongly linear languages is similarly defined. After examining the closure properties of the family of strongly context-free languages, we prove that any slender context-free language is strongly linear. We then show that there are languages of a bounded complexity in terms of the number of …
Authors
Ilie L; Păun G; Rozenberg G; Salomaa A
Journal
Discrete Applied Mathematics, Vol. 103, No. 1-3, pp. 153–165
Publisher
Elsevier
Publication Date
7 2000
DOI
10.1016/s0166-218x(99)00239-5
ISSN
0166-218X