Improved descriptional complexity results on generalized forbidding grammars
From MaRDI portal
Publication:5918761
DOI10.1016/j.dam.2020.12.027OpenAlexW4244485782MaRDI QIDQ5918761
Rufus O. Oladele, Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman
Publication date: 4 August 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2020.12.027
computational completenesssemi-conditional grammarsgeneralized forbidding grammarsdescriptional complexity in formal languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of permitting features in cooperating context-free array grammar systems
- A note on the descriptional complexity of semi-conditional grammars
- Descriptional complexity of context-free grammar forms
- Nonterminal complexity of programmed grammars.
- Forbidding ET0L grammars.
- A shrinking lemma for random forbidding context languages
- Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
- New nonterminal complexity results for semi-conditional grammars
- On the descriptional complexity of some rewriting mechanisms regulated by context conditions
- PC grammar systems with five context-free components generate all recursively enumerable languages.
- Simple restriction in context-free rewriting
- Contextual array grammars with matrix control, regular control languages, and tissue P systems control
- Nonterminal complexity of one-sided random context grammars
- Parsing Beyond Context-Free Grammars
- Generalized forbidding grammars
- Normal forms for phrase-structure grammars
- On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
- Descriptional Complexity Of Generalized Forbidding Grammars
- Regulated Grammars and Automata
- Grammars with Context Conditions and Their Applications
- Improved descriptional complexity results on generalized forbidding grammars
This page was built for publication: Improved descriptional complexity results on generalized forbidding grammars
