On the computational completeness of generalized forbidding matrix grammars

DOI10.1016/J.TCS.2024.114539MaRDI QIDQ6496878

Lakshmanan Kuppusamy, Henning Fernau, Indhumathi Raman

Publication date: 6 May 2024

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

zbMATH Keywords

computational completenessmatrix grammarsdescriptional complexitygeneralized forbidding grammars

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On restricted context-free grammars
• A variant of random context grammars: Semi-conditional grammars
• Petri net algorithms in the theory of matrix grammars
• Nonterminal complexity of programmed grammars.
• Regulated grammars under leftmost derivation
• From regulated rewriting to computing with membranes: collapsing hierarchies
• Generalized forbidding matrix grammars and their membrane computing perspective
• A note on leftmost restricted random context grammars
• Six nonterminals are enough for generating each r.e. language by a matrix grammar
• Generalized forbidding grammars
• Normal forms for phrase-structure grammars
• Descriptional Complexity Of Generalized Forbidding Grammars
• ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS
• Matrix grammars with a leftmost restriction
• Improved descriptional complexity results on generalized forbidding grammars

This page was built for publication: On the computational completeness of generalized forbidding matrix grammars