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

DOI10.1007/978-3-319-60134-2_8MaRDI QIDQ2399250zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, 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)

Recommendations

• On path-controlled insertion-deletion systems
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Graph-controlled insertion-deletion systems
• Descriptional complexity of graph-controlled insertion-deletion systems
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes

Cites work

• About one-sided one-symbol insertion-deletion P systems
• An essay on general grammars
• Contextual insertions/deletions and computability
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 3307580 (Why is no real title available?)
• Insertion-Deletion Systems with One-Sided Contexts
• Normal forms for phrase-structure grammars
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On the computational power of insertion-deletion systems
• Parikh images of matrix ins-del systems
• Recent developments on insertion-deletion systems

Cited in

(8)

• On path-controlled insertion-deletion systems
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• Descriptional complexity of graph-controlled insertion-deletion systems
• scientific article; zbMATH DE number 64179 (Why is no real title available?)
• On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
• Graph-controlled insertion-deletion systems
• On the generative capacity of matrix insertion-deletion systems of small sum-norm

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

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