On the computational completeness of matrix simple semi-conditional grammars

DOI10.1016/J.IC.2021.104688MaRDI QIDQ2113382zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

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)

Recommendations

• Descriptional complexity of matrix simple semi-conditional grammars
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
• On the computational completeness of generalized forbidding matrix grammars
• Simple matrix grammars and their leftmost variants

Cites work

• scientific article; zbMATH DE number 21368 (Why is no real title available?)
• scientific article; zbMATH DE number 3545184 (Why is no real title available?)
• scientific article; zbMATH DE number 709441 (Why is no real title available?)
• scientific article; zbMATH DE number 2012396 (Why is no real title available?)
• scientific article; zbMATH DE number 1870506 (Why is no real title available?)
• A note on the descriptional complexity of semi-conditional grammars
• A variant of random context grammars: Semi-conditional grammars
• Descriptional complexity of matrix simple semi-conditional grammars
• From regulated rewriting to computing with membranes: collapsing hierarchies
• New nonterminal complexity results for semi-conditional grammars
• Nonterminal complexity of programmed grammars.
• Normal forms for phrase-structure grammars
• On erasing productions in random context grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• On the power of permitting semi-conditional grammars
• Petri net algorithms in the theory of matrix grammars
• Programmed Grammars and Classes of Formal Languages
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Simple-semi-conditional versions of matrix grammars with a reduced regulating mechanism

Cited in

(7)

• Prescribed teams of rules working on several objects
• Pareto grammars
• A reformulation of matrix graph grammars with Boolean complexes
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• scientific article; zbMATH DE number 3902057 (Why is no real title available?)
• On the computational completeness of generalized forbidding matrix grammars
• Star-controlled insertion-deletion systems describing regular closure of linear languages

This page was built for publication: On the computational completeness 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 Q2113382)