Some descriptional complexity results for context-conditional grammars

DOI10.1007/978-3-032-32016-2_5MaRDI QIDQ7412087zbMATH OpenFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman, Silas Cato Sacher

Publication date 2027

Full work available at URL https://doi.org/10.1007/978-3-032-32016-2_5

zbMATH Keywords

computational completenesscontext-conditional grammarsregulated rewriting

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
• A variant of random context grammars: Semi-conditional grammars
• Counting simple rules in semi-conditional grammars is not simple
• Descriptional complexity of semi-conditional grammars
• Generalized forbidding grammars
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• Improved descriptional complexity results on generalized forbidding grammars
• New nonterminal complexity results for semi-conditional grammars
• Non-simple rule counting in semi-conditional grammars
• Normal forms for phrase-structure grammars
• On restricted context-free grammars
• On the generative capacity of conditional grammars

This page was built for publication: Some descriptional complexity results for context-conditional grammars

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