On the generative capacity of matrix insertion-deletion systems of small sum-norm

DOI10.1007/S11047-021-09866-YzbMath1530.68134OpenAlexW3198237624MaRDI QIDQ6095512

Lakshmanan Kuppusamy, Henning Fernau, Indhumathi Raman

Publication date: 8 September 2023

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11047-021-09866-y

zbMATH Keywords

computational completenessdescriptional complexityinsertion-deletion systemsmatrix controllinear languagesregular closure

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (1)

When Stars Control a Grammar's Work

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
• Computational power of insertion-deletion (P) systems with rules of size two
• P systems with minimal insertion and deletion
• Recent developments on insertion-deletion systems
• Contextual insertions/deletions and computability
• Matrix insertion-deletion systems
• Insertion languages
• Adding matrix control: insertion-deletion systems with substitutions. III
• DNA computing: Arrival of biological mathematics
• Context-free insertion-deletion systems
• Computational completeness of simple semi-conditional insertion-deletion systems
• Universal insertion grammars of size two
• On matrix ins-del systems of small sum-norm
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• Universal matrix insertion grammars with small size
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• Random Context and Semi-conditional Insertion-deletion Systems
• Parikh Images of Matrix Ins-Del Systems
• On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
• Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
• Investigations on the power of matrix insertion-deletion systems with small sizes

This page was built for publication: On the generative capacity of matrix insertion-deletion systems of small sum-norm