Insertion-Deletion Systems with One-Sided Contexts

DOI10.1007/978-3-540-74593-8_18zbMath1155.68419OpenAlexW1601325472MaRDI QIDQ3608484

Sergey Verlan, Yurii Rogozhin, Artiom Matveevici

Publication date: 5 March 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74593-8_18

zbMATH Keywords

universalityinsertion-deletion systemscomputational non-completeness

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (18)

Insertion-deletion systems with substitutions I ⋮ Circular Post Machines and P Systems with Exo-insertion and Deletion ⋮ Parsimonious computational completeness ⋮ Universality in Molecular and Cellular Computing ⋮ Computational completeness of path-structured graph-controlled insertion-deletion systems ⋮ Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States ⋮ P systems with minimal insertion and deletion ⋮ Single semi-contextual insertion-deletion systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ When Stars Control a Grammar's Work ⋮ Unnamed Item ⋮ On path-controlled insertion-deletion systems ⋮ Further Results on Insertion-Deletion Systems with One-Sided Contexts ⋮ Universal insertion grammars of size two ⋮ Computational power of insertion-deletion (P) systems with rules of size two ⋮ Matrix insertion-deletion systems ⋮ Insertion-deletion systems with substitutions. I

This page was built for publication: Insertion-Deletion Systems with One-Sided Contexts