Descriptional complexity of matrix simple semi-conditional grammars

DOI10.1007/978-3-030-23247-4_8MaRDI QIDQ2179331zbMATHOpenAlexFDO

Authors 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

zbMATH Keywords

computational completenessmatrix grammarsdescriptional complexitysimple semi-conditional grammarsGeffert normal forms

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

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

Cited in

(7)

• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• Parsimonious computational completeness
• On the computational completeness of generalized forbidding matrix grammars
• Simple-semi-conditional versions of matrix grammars with a reduced regulating mechanism
• Simple matrix grammars and their leftmost variants
• Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
• On the computational completeness of matrix 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)