Insertion-Deletion Systems with One-Sided Contexts

DOI10.1007/978-3-540-74593-8_18MaRDI QIDQ3608484zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(23)

• On path-controlled insertion-deletion systems
• Parsimonious computational completeness
• Computational power of insertion-deletion (P) systems with rules of size two
• P systems with minimal insertion and deletion
• On Szilard languages of InsDel systems
• Single semi-contextual insertion-deletion systems
• Recent developments on insertion-deletion systems
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• Matrix insertion-deletion systems
• Insertion-deletion systems with substitutions. I
• Universality of graph-controlled leftist insertion-deletion systems with two states
• Insertion-deletion systems with substitutions. I
• 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
• scientific article; zbMATH DE number 7584595 (Why is no real title available?)
• 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)