Non-closure under complementation for unambiguous linear grammars
From MaRDI portal
Publication:6040667
DOI10.1016/j.ic.2023.105031arXiv2210.02329OpenAlexW4361302750MaRDI QIDQ6040667
Alexander Okhotin, Olga Martynova
Publication date: 19 May 2023
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2210.02329
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Deciding regularity of hairpin completions of regular languages in polynomial time
- On the growth of linear languages
- Bounded languages described by GF(2)-grammars
- Analytic models and ambiguity of context-free languages
- On multiple context-free grammars
- A tale of conjunctive grammars
- Semigroups, Presburger formulas, and languages
- Bounded Algol-Like Languages
- Preservation of unambiguity and inherent ambiguity in context-free languages
- The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
This page was built for publication: Non-closure under complementation for unambiguous linear grammars