Insertion-deletion systems with substitutions. I

DOI10.3233/COM-210345MaRDI QIDQ5037217zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational completenesscontext-sensitive languagesdeletionsinsertionssustitutions

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(18)

• Insertion-deletion systems over relational words
• 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
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• Adding matrix control: insertion-deletion systems with substitutions. III
• Decidability questions for insertion systems and related models
• On the weight of universal insertion grammars
• Block substitutions and their properties
• Insertion-deletion with substitutions. II: About the role of one-sided context
• 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)