A Note on Nested String Replacements

2016/07/06 by Holger Petersen, Petersen, Holger
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · pdf · doi:10.48550/arxiv.1607.01828

openalex publication_date 2016/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the number of nested string replacements required to reduce a string of identical characters to one character.

Related

• Asymptotically Optimal Codes Correcting One Substring Edit
• Minimal unique palindromic substrings after single-character substitution
• Directed Replacement
• Codes Correcting Two Deletions
• Single-Deletion Single-Substitution Correcting Codes