Insertion-deletion systems with substitutions I

DOI10.3233/COM-210345zbMath1490.68132OpenAlexW3206287727MaRDI QIDQ5037217

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)

Related Items

Unnamed Item

Cites Work

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