Investigations on the power of matrix insertion-deletion systems with small sizes

DOI10.1007/s11047-017-9656-8zbMath1528.68161DBLPjournals/nc/FernauKR18OpenAlexW2773559383WikidataQ59864859 ScholiaQ59864859MaRDI QIDQ6061993

Indhumathi Raman, Henning Fernau, Lakshmanan Kuppusamy

Publication date: 30 November 2023

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

Full work available at URL: https://doi.org/10.1007/s11047-017-9656-8

zbMATH Keywords

computational completenessdescriptional complexitymatrix controlmatrix ins-del systemsmetalinear languages

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (4)

Parsimonious computational completeness ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ Single semi-contextual insertion-deletion systems ⋮ Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
• P systems with minimal insertion and deletion
• Recent developments on insertion-deletion systems
• Contextual insertions/deletions and computability
• Matrix insertion-deletion systems
• On the reachability problem for 5-dimensional vector addition systems
• Small deterministic Turing machines
• Nonterminal complexity of programmed grammars.
• On the computational power of insertion-deletion systems
• Context-free insertion-deletion systems
• Finite turns and the regular closure of linear context-free languages
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• 2-state 2-symbol Turing machines with periodic support produce regular sets
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Recent advances in formal languages and applications.
• Random Context and Semi-conditional Insertion-deletion Systems
• Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion
• The Complexity of Small Universal Turing Machines: A Survey
• On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems
• Parikh Images of Matrix Ins-Del Systems
• Automata Studies. (AM-34)
• Six nonterminals are enough for generating each r.e. language by a matrix grammar
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Normal forms for phrase-structure grammars
• Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
• One-sided and two-sided context in formal grammars
• On Context-Free Languages
• The Halting Problem of one State Turing Machines with n‐Dimensional Tape
• Classes of languages and linear-bounded automata

This page was built for publication: Investigations on the power of matrix insertion-deletion systems with small sizes