%0 Conference Proceedings
%T How Much Different Are Two Words with Different Shortest Periods
%+ King‘s College London
%+ Université Paris-Est Marne-la-Vallée (UPEM)
%+ University of Warsaw (UW)
%A Alzamel, Mai
%A Crochemore, Maxime
%A Iliopoulos, Costas, S.
%A Kociumaka, Tomasz
%A Kundu, Ritu
%A Radoszewski, Jakub
%A Rytter, Wojciech
%A Waleń, Tomasz
%Z Part 3: MHDW
%< avec comité de lecture
%( IFIP Advances in Information and Communication Technology
%B 14th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI)
%C Rhodes, Greece
%Y Lazaros Iliadis
%Y Ilias Maglogiannis
%Y Vassilis Plagianakos
%I Springer International Publishing
%3 Artificial Intelligence Applications and Innovations
%V AICT-520
%P 168-178
%8 2018-05-25
%D 2018
%R 10.1007/978-3-319-92016-0_16
%Z Computer Science [cs]Conference papers
%X 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'$$p′ which divides p. For integers p, n ($$p\le n$$p≤n) we define $$\mathcal {P}_{p}(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 $$p\ne q$$p≠q and $$n \ge \max (p,q)$$n≥max(p,q). $$\begin{aligned} {\mathcal D}_{p,q}(n) = \min \,\{\, dist (x,y)\,:\; x\in \mathcal {P}_{p}(n), \,y\in \mathcal {P}_{q}(n)\,\}, \\ N_{p,q}(h) = \max \,\{\, n \,:\; {\mathcal D}_{p,q}(n)\le h\,\}. \qquad \qquad \end{aligned}$$Dp,q(n)=min{dist(x,y):x∈Pp(n),y∈Pq(n)},Np,q(h)=max{n:Dp,q(n)≤h}.
%G English
%Z TC 12
%Z WG 12,5
%2 https://inria.hal.science/hal-01821339/document
%2 https://inria.hal.science/hal-01821339/file/468652_1_En_16_Chapter.pdf
%L hal-01821339
%U https://inria.hal.science/hal-01821339
%~ IFIP
%~ IFIP-AICT
%~ IFIP-TC
%~ IFIP-WG
%~ IFIP-TC12
%~ IFIP-AIAI
%~ IFIP-WG12-5
%~ IFIP-AICT-520
%~ UNIV-EIFFEL
%~ UPEM-UNIVEIFFEL