Computational power of insertion-deletion (P) systems with rules of size two

DOI10.1007/S11047-010-9208-YzbMath1217.68094OpenAlexW1994351002MaRDI QIDQ553921

Sergey Verlan, Alexander Krassovitskiy, Yurii Rogozhin

Publication date: 28 July 2011

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11047-010-9208-y

zbMATH Keywords

universalitydecidabilityP systemscomputational completenessinsertion-deletion systems

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (18)

On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Insertion-deletion systems with substitutions I ⋮ Circular Post Machines and P Systems with Exo-insertion and Deletion ⋮ Adding matrix control: insertion-deletion systems with substitutions. III ⋮ Parsimonious computational completeness ⋮ Outfix-guided insertion ⋮ 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 ⋮ Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1) ⋮ State Complexity of Insertion ⋮ Unnamed Item ⋮ On path-controlled insertion-deletion systems ⋮ Outfix-Guided Insertion ⋮ Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems ⋮ Insertion-deletion systems with substitutions. I ⋮ Generating and accepting P systems with minimal left and right insertion and deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• P systems with minimal insertion and deletion
• Contextual insertions/deletions and computability
• Characterizations of recursively enumerable languages by means of insertion grammars
• On the computational power of insertion-deletion systems
• Context-free insertion-deletion systems
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts

This page was built for publication: Computational power of insertion-deletion (P) systems with rules of size two