5
$\begingroup$

I wish to ask a problem in periodic strings, it might be well-known but I am a beginner in this subject, so I am very glad if someones can show me. My problem is that can we add some string to the end of a periodic string ($S$) to have a new periodic string ($S'$)? If yes, what are the conditions?

More formally, given $$S = [a_1 a_2 ... a_n]_t$$​ - S is a periodic string (a string of $t$ repeated string $a_1 a_2 ... a_n$​), where $n > 1$ and $t > 1$ and $a_i∈ A$ where $A$ is the alphabet (here we only consider the minimal $n$ such that $S$ is a period string - there does not exist $n'<n$ such that $S$ is a period string of consecutive strings of length $n'$). Suppose that if we concatenate a string [$c_1 c_2...c_k$] to $S$ ($c_j∈ A$​ for all $j = 1,...,k$), then we have: $$S' = [a_1 a_2 ... a_n]_t [c_1 c_2...c_k].$$​ So, does there exist the positive integers $m, s (m>1,s>1)$ such that $S' = [a_{\pi(1)}...a_{π(m)}]_s$​ - another periodic string, where $π$ is some permutation from $\mathbf N$ to $\mathbf N$? If yes, what are the conditions? And are there some good algorithms to test this problem?

We see a trivial case when $[c_1 c_2...c_k] = [a_1 a_2 ... a_n]_v$ for any $v \in \mathbf N^*$. Do we have other cases? Could someone show me some researchs in this problem?

Thank you very much for your attention!

Improve this question
$\endgroup$
7
  • $\begingroup$ There is a substantial literature on infinite strings which have substrings of fractional periods, e.g.w=s^{7/3}. The name James Currie comes to mind. However, you assume a minimality condition which often does not occur. If this holds, then I do not see any other cases that would occur, and if the a_i are letters and not words, then you probably have very little left to conclude your analysis. Gerhard "Repeats Himself Sometimes Repeats Himself" Paseman, 2016.03.22. $\endgroup$
    – Gerhard Paseman
    Commented Mar 22, 2016 at 15:35
  • 1
    $\begingroup$ Without restrictions on $k$ (for example $k<nt$) there are stupid example, e.g. $[ab]_2+[bababb]=[ababb]_2.$ $\endgroup$
    – Mikhail Ivanov
    Commented Mar 22, 2016 at 17:17
  • $\begingroup$ @MikhailIvanov: Nice! I am curios particularly about the case $k < n$(certainly it is not the condition for this problem). Do you have any idea? $\endgroup$
    – Cuong
    Commented Mar 22, 2016 at 17:39
  • $\begingroup$ Are you restricting $t$ to be an integer? $\endgroup$
    – JRN
    Commented Mar 23, 2016 at 0:40
  • 1
    $\begingroup$ Here is a nontrivial example: $[abaababa]_2 = [abaab]_2 [aababa]$. $\endgroup$
    – Douglas Zare
    Commented Mar 23, 2016 at 5:43

1 Answer 1

Reset to default
2
$\begingroup$

I'll use exponents instead of subscripts to show repetition.

To have nontrivial examples, the power of the longer word must be two or three, and you can't have two complete repetitions of the longer word within the power of the shorter word. For example, $[abababa]^2$ is a prefix of $[abababaab]^2$ and $[abababaab]^3$.

It suffices to consider the case that the words have lengths that are relatively prime. Otherwise, a nontrivial example would force the existence of a nontrivial example on a subsequence. So, assume the words have coprime lengths, so the shorter has length $m$ and the longer has length $n$.

If the powers of the shorter word contain the square of the longer word and the lengths are coprime, this forces a chain of equalities connecting every position. Consider $a_0=a_n=a_{n-m}=...$ where at each step the index increases by $n$ or decreases by $m$, and the index stays smaller than $2n$. The indices cover every residue class mod $m$ since $n$ and $m$ are coprime, so this forces $a_0=a_1=...=a_{m-1}$ and thus if these are the minimal periods, $m=n=1$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ What I said about the coprime case being the essential one is true, but the argument I gave for the reduction doesn't quite work since it is possible for the subsequences to be trivial in incompatible ways so that the whole sequence is nontrivial while the subsequences are not, However, it is true that if there is a nontrivial example when the lengths are not coprime then you can factor out the common factor by passing to a larger alphabet. $\endgroup$
    – Douglas Zare
    Commented Mar 24, 2016 at 0:14
  • $\begingroup$ Thank you very much, Douglas, for your idea of coprime case. I am thinking about your suggestion, I hope that it could work for the general case. $\endgroup$
    – Cuong
    Commented Mar 24, 2016 at 7:24
  • $\begingroup$ This covers the general case. $\endgroup$
    – Douglas Zare
    Commented Mar 24, 2016 at 7:41
  • $\begingroup$ I don't understand why "the power of the longer word must be two or three" and what you mean by "you can't have two complete repetitions of the longer word within the power of the shorter word". Could you write it more formally by equations and proofs when you have time? $\endgroup$
    – Cuong
    Commented Mar 24, 2016 at 8:06
  • $\begingroup$ If the power of the longer word is greater than three, then in the first half (contained in the square of the shorter word), there is a square of the longer word, which can't happen, as I proved in the last paragraph. $\endgroup$
    – Douglas Zare
    Commented Mar 24, 2016 at 16:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .