Nonterminal complexity of one-sided random context grammars
From MaRDI portal
Publication:2428495
DOI10.1007/s00236-012-0150-6zbMath1284.68330MaRDI QIDQ2428495
Publication date: 26 April 2012
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00236-012-0150-6
Related Items
Improved descriptional complexity results on generalized forbidding grammars, One-sided random context grammars with a limited number of right random context rules, One-Sided Random Context Grammars: A Survey, One-Sided Random Context Grammars with Leftmost Derivations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Scattered context grammars generate any recursively enumerable language with two nonterminals
- One-sided random context grammars
- Descriptional complexity of multi-parallel grammars
- A note on the descriptional complexity of semi-conditional grammars
- On the descriptional complexity of scattered context grammars
- A simultaneous reduction of several measures of descriptional complexity in scattered context grammars
- Nonterminal complexity of programmed grammars.
- On the descriptional complexity of some rewriting mechanisms regulated by context conditions
- On the descriptional complexity of Watson-Crick automata
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Normal forms for phrase-structure grammars