Necessary conditions for subclasses of random context languages

DOI10.1016/J.TCS.2012.12.038MaRDI QIDQ1939280zbMATH OpenOpenAlexFDO

Authors Sigrid Ewert, Andries van der Walt

Publication date 4 March 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.12.038

zbMATH Keywords

context-free languageformal languagenecessary conditionrandom context languagerandom forbidding context languagerandom permitting context languageregulated rewriting

Mathematics Subject Classification ID

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

Recommendations

• A shrinking lemma for random forbidding context languages
• Random languages for nonuniform complexity classes
• A pumping lemma for random permitting context languages
• scientific article; zbMATH DE number 637483
• Some subclasses of context-free languages in NC^ 1
• On Languages Reducible to Algorithmically Random Languages
• On complexity classes and algorithmically random languages (extended abstract)
• A hierarchy of random-context grammars and automata
• Nonuniform complexity and the randomness of certain complete languages
• Remarks on some simple variants of random context grammars

Cited in

(5)

• A shrinking lemma for random forbidding context languages
• Necessary conditions for subclasses of random context galleries
• Ogden's lemma for subclasses of random context galleries
• A pumping lemma for permitting semi-conditional languages
• A pumping lemma for random permitting context languages

This page was built for publication: Necessary conditions for subclasses of random context languages

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