On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes

DOI10.25596/JALC-2017-061MaRDI QIDQ4609328zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Publication date 29 March 2018

Full work available at URL https://doi.org/10.25596/jalc-2017-061

zbMATH Keywords

computational completenessdescriptional complexity measuresgraph-controlled systemsinsertion-deletion systemsmetalinear languages

Mathematics Subject Classification ID

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

Recommendations

• Generative power of matrix insertion-deletion systems with context-free insertion or deletion
• On the power of generalized forbidding insertion-deletion systems
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On the computational power of insertion-deletion systems
• scientific article; zbMATH DE number 1953225
• Descriptional complexity of graph-controlled insertion-deletion systems
• Computational power of P systems with small size insertion and deletion rules
• Graph-controlled insertion-deletion systems
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• Investigations on the power of matrix insertion-deletion systems with small sizes

Cited in

(15)

• On path-controlled insertion-deletion systems
• On the power of generalized forbidding insertion-deletion systems
• Prescribed teams of rules working on several objects
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• Descriptional complexity of graph-controlled insertion-deletion systems
• On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
• Decidability questions for insertion systems and related models
• Investigations on the power of matrix insertion-deletion systems with small sizes
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
• Subregularly controlled insertion systems
• Adding matrix control: insertion-deletion systems with substitutions. III
• Parsimonious computational completeness

This page was built for publication: On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes

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