Skip to Main content Skip to Navigation
Conference papers

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'$$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}.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01821339
Contributor : Hal Ifip <>
Submitted on : Friday, June 22, 2018 - 2:20:11 PM
Last modification on : Monday, June 8, 2020 - 9:34:13 AM
Long-term archiving on: : Tuesday, September 25, 2018 - 12:55:55 PM

File

468652_1_En_16_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Mai Alzamel, Maxime Crochemore, Costas 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⟩

Share

Metrics

Record views

311

Files downloads

4