King's College London

Research portal

How Much Different Are Two Words with Different Shortest Periods

Research output: Chapter in Book/Report/Conference proceedingChapter

Standard

How Much Different Are Two Words with Different Shortest Periods. / Alzamel, Mai; Crochemore, Maxime; Iliopoulos, Costas S.; Kociumaka, Tomasz; Kundu, Ritu; Radoszewski, Jakub; Rytter, Wojciech; Wale, Tomasz.

Artificial Intelligence Applications and Innovations: AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings. ed. / Lazaros Iliadis; Ilias Maglogiannis; Vassilis Plagianakos. Cham : Springer International Publishing, 2018. p. 168-178.

Research output: Chapter in Book/Report/Conference proceedingChapter

Harvard

Alzamel, M, Crochemore, M, Iliopoulos, CS, Kociumaka, T, Kundu, R, Radoszewski, J, Rytter, W & Wale, T 2018, How Much Different Are Two Words with Different Shortest Periods. in L Iliadis, I Maglogiannis & V Plagianakos (eds), Artificial Intelligence Applications and Innovations: AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings. Springer International Publishing, Cham, pp. 168-178, AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, 25/05/2018. https://doi.org/10.1007/978-3-319-92016-0_16

APA

Alzamel, M., Crochemore, M., Iliopoulos, C. S., Kociumaka, T., Kundu, R., Radoszewski, J., ... Wale, T. (2018). How Much Different Are Two Words with Different Shortest Periods. In L. Iliadis, I. Maglogiannis, & V. Plagianakos (Eds.), Artificial Intelligence Applications and Innovations: AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings (pp. 168-178). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-92016-0_16

Vancouver

Alzamel M, Crochemore M, Iliopoulos CS, Kociumaka T, Kundu R, Radoszewski J et al. How Much Different Are Two Words with Different Shortest Periods. In Iliadis L, Maglogiannis I, Plagianakos V, editors, Artificial Intelligence Applications and Innovations: AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings. Cham: Springer International Publishing. 2018. p. 168-178 https://doi.org/10.1007/978-3-319-92016-0_16

Author

Alzamel, Mai ; Crochemore, Maxime ; Iliopoulos, Costas S. ; Kociumaka, Tomasz ; Kundu, Ritu ; Radoszewski, Jakub ; Rytter, Wojciech ; Wale, Tomasz. / How Much Different Are Two Words with Different Shortest Periods. Artificial Intelligence Applications and Innovations: AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings. editor / Lazaros Iliadis ; Ilias Maglogiannis ; Vassilis Plagianakos. Cham : Springer International Publishing, 2018. pp. 168-178

Bibtex Download

@inbook{b3a81111a154435b901a03eef1e95859,
title = "How Much Different Are Two Words with Different Shortest Periods",
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.",
author = "Mai Alzamel and Maxime Crochemore and Iliopoulos, {Costas S.} and Tomasz Kociumaka and Ritu Kundu and Jakub Radoszewski and Wojciech Rytter and Tomasz Wale",
year = "2018",
doi = "10.1007/978-3-319-92016-0_16",
language = "Undefined/Unknown",
isbn = "9783319920160",
pages = "168--178",
editor = "Lazaros Iliadis and Ilias Maglogiannis and Vassilis Plagianakos",
booktitle = "Artificial Intelligence Applications and Innovations",
publisher = "Springer International Publishing",

}

RIS (suitable for import to EndNote) Download

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

ER -

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454