Random context and semi-conditional insertion-deletion systems

DOI10.3233/FI-2015-1203zbMATH Open1357.68060arXiv1112.5947OpenAlexW1940239034MaRDI QIDQ2805451FDOQ2805451

Authors: Sergiu Ivanov, Sergey Verlan 

Publication date: 11 May 2016

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: In this article we introduce the operations of insertion and deletion working in a random-context and semi-conditional manner. We show that the conditional use of rules strictly increase the computational power. In the case of semi-conditional insertion-deletion systems context-free insertion and deletion rules of one symbol are sufficient to get the computational completeness. In the random context case our results expose an asymmetry between the computational power of insertion and deletion rules: systems of size $(2,0,0;1,1,0)$ are computationally complete, while systems of size $(1,1,0;2,0,0)$ (and more generally of size $(1,1,0;p,1,1)$) are not. This is particularly interesting because other control mechanisms like graph-control or matrix control used together with insertion-deletion systems do not present such asymmetry.

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

Recommendations

• Single semi-contextual insertion-deletion systems
• Context-free insertion-deletion systems
• Insertion-Deletion Systems with One-Sided Contexts
• Computational completeness of simple semi-conditional insertion-deletion systems
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• scientific article; zbMATH DE number 3917717
• Contextual insertions/deletions and computability
• On minimal context-free insertion-deletion systems
• Restricted insertion-deletion systems
• On the computational power of insertion-deletion systems

zbMATH Keywords

insertion-deletion systemsrandom contextcomputational (in)completeness

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cited In (19)

• Generating and accepting P systems with minimal left and right insertion and deletion
• On path-controlled insertion-deletion systems
• Single semi-contextual insertion-deletion systems
• Computational power of insertion-deletion (P) systems with rules of size two
• Insertion-deletion systems with substitutions. I
• Matrix insertion-deletion systems
• Universality of graph-controlled leftist insertion-deletion systems with two states
• Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)
• Computational completeness of simple semi-conditional insertion-deletion systems
• Contextual insertions/deletions and computability
• Universality and computational completeness of controlled leftist insertion-deletion systems
• Decidability questions for insertion systems and related models
• 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
• 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
• Title not available (Why is that?)
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts

This page was built for publication: Random context and semi-conditional insertion-deletion systems

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