On the computational completeness of matrix simple semi-conditional grammars

DOI10.1016/J.IC.2021.104688OpenAlexW3118996768MaRDI QIDQ2113382

Indhumathi Raman, Lakshmanan Kuppusamy, Henning Fernau

Publication date: 14 March 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2021.104688

zbMATH Keywords

computational completenessmatrix grammarsdescriptional complexitysemi-conditional grammars

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Prescribed teams of rules working on several objects

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the descriptional complexity of semi-conditional grammars
• A variant of random context grammars: Semi-conditional grammars
• Petri net algorithms in the theory of matrix grammars
• Nonterminal complexity of programmed grammars.
• New nonterminal complexity results for semi-conditional grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• From regulated rewriting to computing with membranes: collapsing hierarchies
• Descriptional complexity of matrix simple semi-conditional grammars
• On the power of permitting semi-conditional grammars
• On Erasing Productions in Random Context Grammars
• Normal forms for phrase-structure grammars
• Programmed Grammars and Classes of Formal Languages

This page was built for publication: On the computational completeness of matrix simple semi-conditional grammars