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
computational completenessdescriptional complexityinsertion-deletion systemssimple semi-conditionalspecial Geffert normal form
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)