DETERMINISTIC CONSTRUCTION OF SYNCHRONIZATION STRING OVER SMALL ALPHABET

Synchronization string;deterministic;Computer Science

Wu, KeLi, Xin ;

Johns Hopkins University

关键词: Synchronization string;    deterministic;    Computer Science;   

Others  :  https://jscholarship.library.jhu.edu/bitstream/handle/1774.2/58697/WU-THESIS-2017.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: JOHNS HOPKINS DSpace Repository

【 摘 要 】

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.