Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
We introduce synchronization strings as a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions. Synchronization errors are strictly more general and much harder to deal with than commonly considered half-errors, i.e., symbol corruptions and erasures. For every $\epsilon >0$, synchronization strings allow to index a sequence …