Nonterminal complexity of one-sided random context grammars

DOI10.1007/S00236-012-0150-6zbMath1284.68330OpenAlexW2015467640MaRDI 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

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (4)

One-Sided Random Context Grammars with Leftmost Derivations ⋮ One-sided random context grammars with a limited number of right random context rules ⋮ One-Sided Random Context Grammars: A Survey ⋮ Improved descriptional complexity results on generalized forbidding grammars

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

This page was built for publication: Nonterminal complexity of one-sided random context grammars