Matrix insertion-deletion systems

DOI10.1016/J.TCS.2012.07.002zbMATH Open1279.68087arXiv1012.5248OpenAlexW1614696623MaRDI QIDQ714867FDOQ714867

Authors: Ion Petre, Sergey Verlan 

Publication date: 11 October 2012

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

Abstract: In this article, we consider for the first time the operations of insertion and deletion working in a matrix controlled manner. We show that, similarly as in the case of context-free productions, the computational power is strictly increased when using a matrix control: computational completeness can be obtained by systems with insertion or deletion rules involving at most two symbols in a contextual or in a context-free manner and using only binary matrices.

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

Recommendations

• scientific article; zbMATH DE number 2087035
• Investigations on the power of matrix insertion-deletion systems with small sizes
• Array insertion and deletion P systems
• Restricted insertion-deletion systems
• Adding matrix control: insertion-deletion systems with substitutions. III
• Insertion-Deletion Systems with One-Sided Contexts
• Graph-controlled insertion-deletion systems
• Insertion-deletion systems over relational words
• On the computational power of insertion-deletion systems
• scientific article; zbMATH DE number 1953225

zbMATH Keywords

computational completenessformal languagesinsertion-deletion systemsmatrix control

Mathematics Subject Classification ID

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

Cites Work

• 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
• Normal forms for phrase-structure grammars
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph-controlled insertion-deletion systems
• Title not available (Why is that?)
• Insertion languages
• Marcus contextual grammars
• On the computational power of insertion-deletion systems
• On minimal context-free insertion-deletion systems
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts
• Contextual insertions/deletions and computability
• Small size insertion and deletion systems
• Title not available (Why is that?)
• Computational power of P systems with small size insertion and deletion rules

Cited In (23)

• Generating and accepting P systems with minimal left and right insertion and deletion
• On path-controlled insertion-deletion systems
• Prescribed teams of rules working on several objects
• Single semi-contextual insertion-deletion systems
• On Szilard languages of InsDel systems
• Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
• Generative power of matrix insertion-deletion systems with context-free insertion or deletion
• Adding matrix control: insertion-deletion systems with substitutions. III
• Investigations on the power of matrix insertion-deletion systems with small sizes
• Parikh images of matrix ins-del systems
• The matrix as in-situ data structure
• Universal insertion grammars of size two
• On succinct description of certain context-free languages by ins-del and matrix ins-del systems
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• On matrix ins-del systems of small sum-norm
• Graph-controlled insertion-deletion systems
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
• Universal matrix insertion grammars with small size
• When Stars Control a Grammar's Work
• Title not available (Why is that?)
• On languages generated by context-free matrix insertion-deletion systems with exo-operations
• Descriptional complexity of graph-controlled insertion-deletion systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714867)