TY - CHAP
T1 - How Much Different Are Two Words with Different Shortest Periods
AU - Alzamel, Mai
AU - Crochemore, Maxime
AU - Iliopoulos, Costas S.
AU - Kociumaka, Tomasz
AU - Kundu, Ritu
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Wale, Tomasz
PY - 2018
Y1 - 2018
N2 - Sometimes the difference between two distinct words of the same length cannot be smaller than a certain minimal amount. In particular if two distinct words of the same length are both periodic or quasiperiodic, then their Hamming distance is at least 2. We study here how the minimum Hamming distance dist (x,y)dist(x,y)between two words x, y of the same length n depends on their periods. Similar problems were considered in [1] in the context of quasiperiodicities. We say that a period p of a word x is primitive if x does not have any smaller period p'ptextasciiacutexwhich divides p. For integers p, n (pbackslashle np≤n) we define backslashmathcal Pp(n)Pp(n)as the set of words of length n with primitive period p. We show several results related to the following functions introduced in this paper for pbackslashne qp≠qand n backslashge backslashmax (p,q)n≥max(p,q). backslashbeginaligned backslashmathcal Dp,q(n) = backslashmin backslash,backslashbackslash, dist (x,y)backslash,:backslash; xbackslashin backslashmathcal Pp(n), backslash,ybackslashin backslashmathcal Pq(n)backslash,backslash, backslashbackslash Np,q(h) = backslashmax backslash,backslashbackslash, n backslash,:backslash; backslashmathcal Dp,q(n)backslashle hbackslash,backslash. backslashqquad backslashqquad backslashendalignedDp,q(n)=mindist(x,y):x∈Pp(n),y∈Pq(n),Np,q(h)=maxn:Dp,q(n)≤h.
AB - Sometimes the difference between two distinct words of the same length cannot be smaller than a certain minimal amount. In particular if two distinct words of the same length are both periodic or quasiperiodic, then their Hamming distance is at least 2. We study here how the minimum Hamming distance dist (x,y)dist(x,y)between two words x, y of the same length n depends on their periods. Similar problems were considered in [1] in the context of quasiperiodicities. We say that a period p of a word x is primitive if x does not have any smaller period p'ptextasciiacutexwhich divides p. For integers p, n (pbackslashle np≤n) we define backslashmathcal Pp(n)Pp(n)as the set of words of length n with primitive period p. We show several results related to the following functions introduced in this paper for pbackslashne qp≠qand n backslashge backslashmax (p,q)n≥max(p,q). backslashbeginaligned backslashmathcal Dp,q(n) = backslashmin backslash,backslashbackslash, dist (x,y)backslash,:backslash; xbackslashin backslashmathcal Pp(n), backslash,ybackslashin backslashmathcal Pq(n)backslash,backslash, backslashbackslash Np,q(h) = backslashmax backslash,backslashbackslash, n backslash,:backslash; backslashmathcal Dp,q(n)backslashle hbackslash,backslash. backslashqquad backslashqquad backslashendalignedDp,q(n)=mindist(x,y):x∈Pp(n),y∈Pq(n),Np,q(h)=maxn:Dp,q(n)≤h.
U2 - 10.1007/978-3-319-92016-0_16
DO - 10.1007/978-3-319-92016-0_16
M3 - Chapter
SN - 9783319920160
SP - 168
EP - 178
BT - Artificial Intelligence Applications and Innovations
A2 - Iliadis, Lazaros
A2 - Maglogiannis, Ilias
A2 - Plagianakos, Vassilis
PB - Springer International Publishing
CY - Cham
Y2 - 25 May 2018 through 27 May 2018
ER -
TY - CHAP
T1 - How to Answer a Small Batch of RMQs or LCA Queries in Practice
AU - Alzamel, Mai
AU - Charalampopoulos, Panagiotis
AU - Iliopoulos, Costas S.
AU - Pissis, Solon P.
PY - 2018
Y1 - 2018
U2 - 10.1007/978-3-319-78825-8_28
DO - 10.1007/978-3-319-78825-8_28
M3 - Conference paper
VL - 10765
T3 - Lecture Notes in Computer Science
SP - 343
EP - 355
BT - Combinatorial Algorithms
A2 - Brankovic, Ljiljana
A2 - Ryan, Joe
A2 - Smyth, William F.
PB - Springer International Publishing
CY - Cham
ER -