Descriptional complexity of matrix simple semi-conditional grammars

DOI10.1007/978-3-030-23247-4_8zbMATH Open1434.68219OpenAlexW2954513813MaRDI QIDQ2179331FDOQ2179331

Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Publication date: 12 May 2020

Full work available at URL: https://hal.inria.fr/hal-02387307/file/480958_1_En_8_Chapter.pdf

Recommendations

• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
• Descriptional complexity of semi-conditional grammars
• New nonterminal complexity results for semi-conditional grammars
• Simple-semi-conditional versions of matrix grammars with a reduced regulating mechanism

zbMATH Keywords

computational completenessmatrix grammarsdescriptional complexitysimple semi-conditional grammarsGeffert normal forms

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cited In (4)

• Simple-semi-conditional versions of matrix grammars with a reduced regulating mechanism
• On the computational completeness of matrix simple semi-conditional grammars
• Parsimonious computational completeness
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars

This page was built for publication: Descriptional complexity of matrix simple semi-conditional grammars

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