King's College London

Research portal

How Much Different Are Two Words with Different Shortest Periods

Research output: Chapter in Book/Report/Conference proceedingChapter

Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Jakub Radoszewski, Wojciech Rytter, Tomasz Wale

Original languageUndefined/Unknown
Title of host publicationArtificial Intelligence Applications and Innovations
Subtitle of host publicationAIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings
EditorsLazaros Iliadis, Ilias Maglogiannis, Vassilis Plagianakos
Place of PublicationCham
PublisherSpringer International Publishing
Pages168-178
Number of pages11
ISBN (Print)9783319920160
DOIs
Publication statusPublished - 2018
EventAIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT - Rhodes, Greece
Duration: 25 May 201827 May 2018

Conference

ConferenceAIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT
CountryGreece
CityRhodes
Period25/05/201827/05/2018

King's Authors

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.

View graph of relations

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