On strongly context-free languages

We investigate the context-free languages whose complements are also contex t-free. We call them strongly context-free languages. The family of strongl y linear languages is similarly defined. After examining the closure proper ties of the family of strongly context-free languages, we prove that any sl ender context-free language is strongly linear. We then show that there are languages of a bounded complexity in terms of the number of non-terminals or productions necessary to generate them, whereas the complexity of their complements is arbitrarily large. (C) 2000 Elsevier Science B.V. All rights reserved.