Matrix insertion-deletion systems

DOI10.1016/j.tcs.2012.07.002zbMath1279.68087arXiv1012.5248OpenAlexW1614696623MaRDI QIDQ714867

Sergey Verlan, Ion Petre

Publication date: 11 October 2012

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

Full work available at URL: https://arxiv.org/abs/1012.5248

zbMATH Keywords

formal languagescomputational completenessinsertion-deletion systemsmatrix control

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (18)

On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Modelling DNA and RNA secondary structures using matrix insertion-deletion systems ⋮ Adding matrix control: insertion-deletion systems with substitutions. III ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ Single semi-contextual insertion-deletion systems ⋮ Unnamed Item ⋮ On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2 ⋮ Unnamed Item ⋮ When Stars Control a Grammar's Work ⋮ On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems ⋮ On path-controlled insertion-deletion systems ⋮ Parikh Images of Matrix Ins-Del Systems ⋮ Universal insertion grammars of size two ⋮ Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion ⋮ Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems ⋮ Prescribed teams of rules working on several objects ⋮ Generating and accepting P systems with minimal left and right insertion and deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Contextual insertions/deletions and computability
• Insertion languages
• On the computational power of insertion-deletion systems
• Marcus contextual grammars
• Context-free insertion-deletion systems
• Membrane computing. An introduction.
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Random Context and Semi-conditional Insertion-deletion Systems
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts
• Normal forms for phrase-structure grammars

This page was built for publication: Matrix insertion-deletion systems