On erasing productions in random context grammars

DOI10.1007/978-3-642-14162-1_15MaRDI QIDQ3587437zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(9)

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

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)