Matrix insertion-deletion systems
From MaRDI portal
Publication:714867
DOI10.1016/j.tcs.2012.07.002zbMath1279.68087arXiv1012.5248OpenAlexW1614696623MaRDI QIDQ714867
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
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