Conference paper

Editor list: Calude, CS; Claude, E; Dinneen, MJ

Publication year: 2004

Pages: 284-295

Journal: Lecture notes in computer science

Volume number: 3340

ISSN: 0302-9743

ISBN: 3-540-24014-4

Conference: 8th International Conference on Developments in Language Theory

Publisher: Springer

Title of series: LECTURE NOTES IN COMPUTER SCIENCE

Abstract: 
Closures of linear context-free languages under Boolean operations are investigated. The intersection closure and the complementation closure are incomparable. By closing these closures under further Boolean operations we obtain several new language families. The hierarchy obtained by such closures of closures is proper up to level four, where it collapses to the Boolean closure which, in turn, is incomparable with several closures of the family of context-free languages. The Boolean closure of the linear context-free languages is properly contained in the Boolean closure of the context-free languages. A characterization of a class of non-unary languages that cannot be expressed as a Boolean formula over the linear context-free languages is presented.

Harvard Citation style: Kutrib, M., Malcher, A. and Wotschke, D. (2004) The Boolean closure of linear context-free languages, Lecture notes in computer science (Schriftenreihe), 3340, pp. 284-295

APA Citation style: Kutrib, M., Malcher, A., & Wotschke, D. (2004). The Boolean closure of linear context-free languages. Lecture notes in computer science (Schriftenreihe). 3340, 284-295.