Insertion-Deletion Systems with One-Sided Contexts

DOI10.1007/978-3-540-74593-8_18zbMATH Open1155.68419OpenAlexW1601325472MaRDI QIDQ3608484FDOQ3608484

Authors: Artiom Matveevici, Yurii Rogozhin, Sergey Verlan 

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

Recommendations

• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• About one-sided one-symbol insertion-deletion P systems
• On minimal context-free insertion-deletion systems
• Random context and semi-conditional insertion-deletion systems
• Insertion-deletion systems with substitutions. I

zbMATH Keywords

universalityinsertion-deletion systemscomputational non-completeness

Mathematics Subject Classification ID

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

Cited In (23)

• On path-controlled insertion-deletion systems
• Parsimonious computational completeness
• Single semi-contextual insertion-deletion systems
• On Szilard languages of InsDel systems
• Computational power of insertion-deletion (P) systems with rules of size two
• P systems with minimal insertion and deletion
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• Recent developments on insertion-deletion systems
• Insertion-deletion systems with substitutions. I
• Insertion-deletion systems with substitutions. I
• Matrix insertion-deletion systems
• Universality of graph-controlled leftist insertion-deletion systems with two states
• Universality and computational completeness of controlled leftist insertion-deletion systems
• Insertion-deletion with substitutions. II: About the role of one-sided context
• Universal insertion grammars of size two
• Circular Post machines and P systems with exo-insertion and deletion
• On minimal context-free insertion-deletion systems
• Random context and semi-conditional insertion-deletion systems
• When Stars Control a Grammar's Work
• Universality in Molecular and Cellular Computing
• Title not available (Why is that?)
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• About one-sided one-symbol insertion-deletion P systems

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

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