Nonterminal complexity of one-sided random context grammars

DOI10.1007/s00236-012-0150-6zbMath1284.68330MaRDI QIDQ2428495

Petr Zemek, Alexander Meduna

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

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item