We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Boolean closure of linear context-free languages.
- Authors
Kutrib, Martin; Malcher, Andreas; Wotschke, Detlef
- 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 a certain level, 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.
- Subjects
BOOLEAN algebra; MATHEMATICAL formulas; COMPARATIVE grammar; MATHEMATICAL complexes; LANGUAGE &; languages; LINEAR algebra
- Publication
Acta Informatica, 2008, Vol 45, Issue 3, p177
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-007-0068-6