Synchronization string, first introduced by Haeupler and Shahrasbi[10], is a strong tool in construction of error correcting codes for in-sertion and deletion errors (insdel codes). Synchronization string pro-vides a way to encode the indices of symbols in a string and makes itpossible to transfer synchronization errors to easier half errors, whichis much better understood.In this paper, we improve the construction in [10] in the followingaspects:• We achieve a smaller alphabet size, reduce the alphabet sizefrom O(ε^−4) in [10] to O(ε^−2).• We give an efficient deterministic construction of synchronization string over alphabet of size O(ε^−3).• We give a near linear deterministic construction of synchronization string over alphabet of size O(ε^−4). This algorithm runs in O(n log^2 log n). Independently, Haeupler andShahrasbi give a linear, deterministic construction for synchronization string over alphabet of ε^−O(1) in their work [11].• We introduce a combinatorial object called synchronization circlewhich enhances the property of synchronization string.
【 预 览 】
附件列表
Files
Size
Format
View
DETERMINISTIC CONSTRUCTION OF SYNCHRONIZATION STRING OVER SMALL ALPHABET