Back to Search
Start Over
Non-closure under complementation for unambiguous linear grammars.
- Source :
-
Information & Computation . Jun2023, Vol. 292, pN.PAG-N.PAG. 1p. - Publication Year :
- 2023
-
Abstract
- The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a particular unambiguous linear grammar is presented, and it is proved that the complement of this language is not defined by any context-free grammar. This also constitutes an alternative proof for the result of Hibbard and Ullian ("The independence of inherent ambiguity from complementedness among context-free languages", JACM , 1966) on the non-closure of the unambiguous languages under complementation. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAMMAR
*AMBIGUITY
*LANGUAGE & languages
Subjects
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 292
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 163746641
- Full Text :
- https://doi.org/10.1016/j.ic.2023.105031