On erasing productions in random context grammars

DOI10.1007/978-3-642-14162-1_15zbMATH Open1288.68145OpenAlexW2150922531MaRDI QIDQ3587437FDOQ3587437

Authors: Georg Zetzsche 

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14162-1_15

Recommendations

• Remarks on some simple variants of random context grammars
• A pumping lemma for random permitting context languages
• A shrinking lemma for random forbidding context languages
• One-sided random context grammars
• scientific article; zbMATH DE number 3974325

Mathematics Subject Classification ID

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

Cited In (9)

• One-sided random context grammars
• On the computational completeness of matrix simple semi-conditional grammars
• A sufficient condition for erasing productions to be avoidable
• On restricted context-free grammars
• TOWARD UNDERSTANDING THE GENERATIVE CAPACITY OF ERASING RULES IN MATRIX GRAMMARS
• A pumping lemma for permitting semi-conditional languages
• Workspace theorems for regular-controlled grammars
• On elimination of erasing rules from E0S grammars
• Erasing in context-free AFLs

This page was built for publication: On erasing productions in random context grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587437)