Computational completeness of path-structured graph-controlled insertion-deletion systems

DOI10.1007/978-3-319-60134-2_8zbMath1410.68185OpenAlexW2617866084MaRDI QIDQ2399250

Lakshmanan Kuppusamy, Henning Fernau, Indhumathi Raman

Publication date: 22 August 2017

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

zbMATH Keywords

computational completenessdescriptional complexity measuresgraph-controlled ins-del systemspath-structured control graph

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (3)

On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ On path-controlled insertion-deletion systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recent developments on insertion-deletion systems
• Contextual insertions/deletions and computability
• On the computational power of insertion-deletion systems
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Parikh Images of Matrix Ins-Del Systems
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts
• Normal forms for phrase-structure grammars
• About One-Sided One-Symbol Insertion-Deletion P Systems

This page was built for publication: Computational completeness of path-structured graph-controlled insertion-deletion systems