P systems with minimal insertion and deletion

DOI10.1016/j.tcs.2010.08.025zbMath1207.68180OpenAlexW2031654631MaRDI QIDQ616500

Alexander Krassovitskiy, Yurii Rogozhin, Sergey Verlan, Artiom Alhazov

Publication date: 10 January 2011

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

Full work available at URL: https://idus.us.es/xmlui/handle/11441/38817

zbMATH Keywords

universalityP systemsmembrane computingrecursively enumerable languagesinsertion-deletion systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (16)

On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Circular Post Machines and P Systems with Exo-insertion and Deletion ⋮ 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 ⋮ On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems ⋮ On path-controlled insertion-deletion systems ⋮ Computational power of insertion-deletion (P) systems with rules of size two ⋮ Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion ⋮ Parallel contextual array insertion deletion P systems and tabled matrix grammars ⋮ Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems ⋮ 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
• Contextual insertions/deletions and computability
• Remarks on blind and partially blind one-way multicounter machines
• Characterizations of recursively enumerable languages by means of insertion grammars
• Marcus contextual grammars
• Context-free insertion-deletion systems
• DNA computing. New computing paradigms.
• Membrane computing. An introduction.
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts

This page was built for publication: P systems with minimal insertion and deletion