Computational completeness of simple semi-conditional insertion-deletion systems

DOI10.1007/978-3-319-92435-9_7MaRDI QIDQ1799363zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Publication date 18 October 2018

Full work available at URL https://doi.org/10.1007/978-3-319-92435-9_7

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• Random context and semi-conditional insertion-deletion systems
• Computational power of insertion-deletion (P) systems with rules of size two
• Computational power of P systems with small size insertion and deletion rules
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Descriptional complexity of graph-controlled insertion-deletion systems

Cited in

(10)

• Parsimonious computational completeness
• Single semi-contextual insertion-deletion systems
• Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)
• Contextual insertions/deletions and computability
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• scientific article; zbMATH DE number 1953225 (Why is no real title available?)
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Computational power of P systems with small size insertion and deletion rules
• Random context and semi-conditional insertion-deletion systems
• scientific article; zbMATH DE number 7584595 (Why is no real title available?)

This page was built for publication: Computational completeness of simple semi-conditional insertion-deletion systems

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