Non-closure under complementation for unambiguous linear grammars
From MaRDI portal
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", J.ACM, 1966) on the non-closure of the unambiguous languages under complementation.
Cites work
- A tale of conjunctive grammars
- Analytic models and ambiguity of context-free languages
- Bounded Algol-Like Languages
- Bounded languages described by GF(2)-grammars
- Deciding regularity of hairpin completions of regular languages in polynomial time
- scientific article; zbMATH DE number 1747449 (Why is no real title available?)
- scientific article; zbMATH DE number 3238653 (Why is no real title available?)
- On multiple context-free grammars
- On the growth of linear languages
- Preservation of unambiguity and inherent ambiguity in context-free languages
- Semigroups, Presburger formulas, and languages
- The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
Cited in
(3)
This page was built for publication: Non-closure under complementation for unambiguous linear grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6040667)
