Further Results on Insertion-Deletion Systems with One-Sided Contexts

DOI10.1007/978-3-540-88282-4_31zbMath1156.68458OpenAlexW1547402515MaRDI QIDQ3540125

Alexander Krassovitskiy, Sergey Verlan, Yurii Rogozhin

Publication date: 20 November 2008

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-88282-4_31

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)

On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Insertion-deletion systems with substitutions I ⋮ Circular Post Machines and P Systems with Exo-insertion and Deletion ⋮ 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 ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ Single semi-contextual insertion-deletion systems ⋮ Unnamed Item ⋮ On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2 ⋮ Unnamed Item ⋮ When Stars Control a Grammar's Work ⋮ Unnamed Item ⋮ On path-controlled insertion-deletion systems ⋮ Computational power of insertion-deletion (P) systems with rules of size two ⋮ Matrix insertion-deletion systems ⋮ Insertion-deletion systems with substitutions. I

Cites Work

• Contextual insertions/deletions and computability
• Characterizations of recursively enumerable languages by means of insertion grammars
• Marcus contextual grammars
• Context-free insertion-deletion systems
• Insertion-Deletion Systems with One-Sided Contexts
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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