Insertion-deletion systems with substitutions. I

DOI10.3233/COM-210345zbMATH Open1490.68132OpenAlexW3206287727MaRDI QIDQ5037217FDOQ5037217

Authors: Martin Vu, Henning Fernau 

Publication date: 28 February 2022

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/com-210345

Recommendations

• Insertion-deletion with substitutions. II
• Adding matrix control: insertion-deletion systems with substitutions. III
• Context-free insertion-deletion systems
• Small size insertion and deletion systems
• Random context and semi-conditional insertion-deletion systems

zbMATH Keywords

computational completenesscontext-sensitive languagesdeletionsinsertionssustitutions

Mathematics Subject Classification ID

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

Cites Work

• Context-free insertion-deletion systems
• Generating and accepting P systems with minimal left and right insertion and deletion
• One-sided and two-sided context in formal grammars
• Computational power of insertion-deletion (P) systems with rules of size two
• Recent developments on insertion-deletion systems
• Insertion languages
• The String-to-String Correction Problem
• Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
• DNA computing: Arrival of biological mathematics
• On the computational power of insertion-deletion systems
• On minimal context-free insertion-deletion systems
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts
• Insertion-deletion systems with substitutions. I
• DNA computing based on splicing: The existence of universal computers
• Small size insertion and deletion systems
• Adding matrix control: insertion-deletion systems with substitutions. III
• Comment on the paper 'Error detection in formal languages'
• Insertion-deletion with substitutions. II
• Parsimonious computational completeness
• Title not available (Why is that?)

Cited In (18)

• Insertion-deletion systems over relational words
• Single semi-contextual insertion-deletion systems
• On Szilard languages of InsDel systems
• P systems with minimal insertion and deletion
• Recent developments on insertion-deletion systems
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• Decidability questions for insertion systems and related models
• Insertion-deletion with substitutions. II: About the role of one-sided context
• Block substitutions and their properties
• Adding matrix control: insertion-deletion systems with substitutions. III
• On the weight of universal insertion grammars
• Insertion-deletion with substitutions. II
• Context-free insertion-deletion systems
• On minimal context-free insertion-deletion systems
• Small size insertion and deletion systems
• Complexity of guided insertion-deletion in RNA-editing
• On rationally controlled one-rule insertion systems
• Insertion-Deletion Systems with One-Sided Contexts

This page was built for publication: Insertion-deletion systems with substitutions. I

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