Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States

DOI10.1007/978-3-319-23111-2_6zbMath1410.68191OpenAlexW2179912206MaRDI QIDQ2945880

Sergey Verlan, Sergiu Ivanov

Publication date: 15 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-23111-2_6

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (4)

On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational complexity of spiking neural P systems
• Contextual insertions/deletions and computability
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• EP-based kinematic control and adaptive fuzzy sliding-mode dynamic control for wheeled mobile robots
• Small universal register machines
• Marcus contextual grammars
• Functional stepped surfaces, flips, and generalized substitutions
• Special relativity over the field of rational numbers
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• The complexity of membership problems for circuits over sets of natural numbers
• 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
• Topological invariants for substitution tilings and their associated $C^\ast$-algebras
• Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems
• About One-Sided One-Symbol Insertion-Deletion P Systems
• Universality of Tag Systems with P = 2

This page was built for publication: Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States