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

DOI10.25596/JALC-2017-061zbMath1390.68305OpenAlexW2759523779MaRDI QIDQ4609328

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 completenessinsertion-deletion systemsdescriptional complexity measuresgraph-controlled systemsmetalinear languages

Mathematics Subject Classification ID

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

Related Items (9)

Adding matrix control: insertion-deletion systems with substitutions. III ⋮ Parsimonious computational completeness ⋮ On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems ⋮ 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 ⋮ On path-controlled insertion-deletion systems ⋮ Decidability Questions for Insertion Systems and Related Models ⋮ Prescribed teams of rules working on several objects

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