Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)

DOI10.1007/S11047-019-09742-WzbMath1530.68135OpenAlexW2947655957MaRDI QIDQ6150989

Lakshmanan Kuppusamy, Indhumathi Raman, Henning Fernau

Publication date: 9 February 2024

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

Full work available at URL: https://doi.org/10.1007/s11047-019-09742-w

zbMATH Keywords

computational completenessdescriptional complexityinsertion-deletion systemssimple semi-conditionalspecial Geffert normal form

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On restricted context-free grammars
• Computational power of insertion-deletion (P) systems with rules of size two
• Recent developments on insertion-deletion systems
• Contextual insertions/deletions and computability
• On the computational power of insertion-deletion systems
• On path-controlled insertion-deletion systems
• Computational completeness of simple semi-conditional insertion-deletion systems
• Simple restriction in context-free rewriting
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• Random Context and Semi-conditional Insertion-deletion Systems
• Normal forms for phrase-structure grammars
• On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
• Grammars with Context Conditions and Their Applications
• Investigations on the power of matrix insertion-deletion systems with small sizes

This page was built for publication: Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)