Abstract
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.
Original language | Undefined/Unknown |
---|---|
Title of host publication | Artificial Intelligence Applications and Innovations |
Subtitle of host publication | AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings |
Editors | Lazaros Iliadis, Ilias Maglogiannis, Vassilis Plagianakos |
Place of Publication | Cham |
Publisher | Springer International Publishing |
Pages | 168-178 |
Number of pages | 11 |
ISBN (Print) | 9783319920160 |
DOIs | |
Publication status | Published - 2018 |
Event | AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT - Rhodes, Greece Duration: 25 May 2018 → 27 May 2018 |
Conference
Conference | AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT |
---|---|
Country/Territory | Greece |
City | Rhodes |
Period | 25/05/2018 → 27/05/2018 |