On the computational completeness of graph-controlled insertion-deletion systems with binary sizes

DOI10.1016/j.tcs.2017.01.019zbMath1371.68085OpenAlexW2583101995WikidataQ59864878 ScholiaQ59864878MaRDI QIDQ2358685

Lakshmanan Kuppusamy, Henning Fernau, Indhumathi Raman

Publication date: 15 June 2017

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.01.019

zbMATH Keywords

P systemscomputational completenessinsertion-deletion systemsdescriptional complexity measuresgraph-controlled systems

Mathematics Subject Classification ID

Related Items (8)

Parsimonious computational completeness ⋮ On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems ⋮ Computational completeness of path-structured graph-controlled insertion-deletion systems ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1) ⋮ When Stars Control a Grammar's Work ⋮ On path-controlled insertion-deletion systems ⋮ Decidability Questions for Insertion Systems and Related Models

Cites Work

• Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
• Computational power of insertion-deletion (P) systems with rules of size two
• P systems with minimal insertion and deletion
• Recent developments on insertion-deletion systems
• Contextual insertions/deletions and computability
• Matrix insertion-deletion systems
• Insertion languages
• On the computational power of insertion-deletion systems
• 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
• Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion
• Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems
• Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Normal forms for phrase-structure grammars
• Length P Systems
• About One-Sided One-Symbol Insertion-Deletion P Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the computational completeness of graph-controlled insertion-deletion systems with binary sizes