Additional Problem 5: Local Periodicity Lemma with One Don't Care Symbol
(Preliminary version)
\(
\def\pgcd{\mathit{gcd}}
\)
Letter $*$ is called a don't care (hole, joker) and stands for any
other letter of the alphabet.
It matches any letter including itself.
For a string $x$ we write $x[i]\approx x[j]$ if the letters $x[i]$ and $x[j]$ are
equal or one of them is the don't care symbol.
An integer $p$ is a local period of $x$ if for each $i\lt |x|-p$ we have $x[i]\approx x[i+p]$.
In Periodicity we presented the periodicity lemma.
Lemma 1 (Periodicity lemma)
If $p$ and $q$ are periods of a word $x$ and satisfy $p+q-\pgcd(p,q)\leq|x|$
then $\pgcd(p,q)$ is also a period of $x$.
Our question is related to an extension of this lemma to
words with one don't care symbol.
For simplicity we assume $p,q$ are relatively prime.
Show the following local periodicity lemma.
Assume $p,q$ are relatively prime and $x$ is a word with one don't care symbol.
Show that if $p$ and $q$ are local periods of $x$ and satisfy $p+q\leq|x|$
then $1$ is also a local period of $x$.
Use the periodicity lemma for standard words.
For $p=5,q=7$ give example of a word $x$ having local periods $p,q$, with one don't care,
such that $|x|=p+q-1$, and $x$ has no local period $1$.
References
-
A. Jez,
Recompression: A simple and powerful technique for word equations,
J. ACM 63(1):4:1-4:51, 2016.
-
T. Kociumaka, J. Radoszewski, W. Rytter, and T. Walen,
A periodicity lemma for partial words,
Inf. Comput. 283 (2022) 104677.