Matrix insertion-deletion systems
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 4160148 (Why is no real title available?)
- scientific article; zbMATH DE number 1236223 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3307580 (Why is no real title available?)
- Computational power of P systems with small size insertion and deletion rules
- Context-free insertion-deletion systems
- Contextual insertions/deletions and computability
- Further Results on Insertion-Deletion Systems with One-Sided Contexts
- Graph-controlled insertion-deletion systems
- Insertion languages
- Insertion-Deletion Systems with One-Sided Contexts
- Marcus contextual grammars
- Membrane computing. An introduction.
- Normal forms for phrase-structure grammars
- On minimal context-free insertion-deletion systems
- On the computational power of insertion-deletion systems
- Random context and semi-conditional insertion-deletion systems
- Regulated RNA rewriting: Modelling RNA editing with guided insertion
- Small size insertion and deletion systems
Cited in
(23)- On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
- On succinct description of certain context-free languages by ins-del and matrix ins-del systems
- On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
- Single semi-contextual insertion-deletion systems
- Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
- When Stars Control a Grammar's Work
- Universal matrix insertion grammars with small size
- On Szilard languages of InsDel systems
- Adding matrix control: insertion-deletion systems with substitutions. III
- On the generative capacity of matrix insertion-deletion systems of small sum-norm
- Generative power of matrix insertion-deletion systems with context-free insertion or deletion
- Generating and accepting P systems with minimal left and right insertion and deletion
- The matrix as in-situ data structure
- On matrix ins-del systems of small sum-norm
- On languages generated by context-free matrix insertion-deletion systems with exo-operations
- On path-controlled insertion-deletion systems
- Prescribed teams of rules working on several objects
- Investigations on the power of matrix insertion-deletion systems with small sizes
- Descriptional complexity of graph-controlled insertion-deletion systems
- Universal insertion grammars of size two
- Parikh images of matrix ins-del systems
- Graph-controlled insertion-deletion systems
- scientific article; zbMATH DE number 7584595 (Why is no real title available?)
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)
