How Much Different Are Two Words with Different Shortest Periods - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

How Much Different Are Two Words with Different Shortest Periods

(1) , (1, 2) , (1) , (3) , (1) , (1, 3) , (3) , (3)
1
2
3
Mai Alzamel
  • Function : Author
  • PersonId : 1033616
Costas S. Iliopoulos
  • Function : Author
  • PersonId : 1012032
Tomasz Kociumaka
  • Function : Author
  • PersonId : 1033618
Ritu Kundu
  • Function : Author
  • PersonId : 1012033
Jakub Radoszewski
  • Function : Author
  • PersonId : 1033619
Wojciech Rytter
  • Function : Author
  • PersonId : 1033620
Tomasz Waleń
  • Function : Author
  • PersonId : 1033621

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'$$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}.
Fichier principal
Vignette du fichier
468652_1_En_16_Chapter.pdf (440.55 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01821339 , version 1 (22-06-2018)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, et al.. How Much Different Are Two Words with Different Shortest Periods. 14th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), May 2018, Rhodes, Greece. pp.168-178, ⟨10.1007/978-3-319-92016-0_16⟩. ⟨hal-01821339⟩
244 View
17 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More