Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related to how many times this sequence is repeated, or can contain a bit either 0 or 1. Following image describes it visually:

enter image description here

On this image repetition is denoted by lower index number nearby ending bracket. The bits need to be expanded are denoted by regular size font.

Each sequence can produce binary sequence (sequence of bits), when we expand it.

The questions are:

  1. Can we create a algorithm, that performs AND on two recursive repeating sequences, without expanding both of them? (The algorithm should produce third recursive repeating sequence, such when we expand it, it is AND on both expanded input sequences).
  2. If the answer for first question is true, how such algorithm will look (for example in pseudo code) ?

Note: In practice, the numbers responsible for repetition may be very large, so expansion of whole sequence is not practical in terms of computation - but if algorithm will need to do it partially, it may be accepted.


1 Answer 1


Let $A,B$ be the two recursive repeating sequences, where $|A| = |B|$. If $|A| = |B| = 1$ then there is nothing to do. Otherwise, either $A$ is of the form $A_1A_2$ or of the form $(A')_k$, where $k > 1$. In the second case, we can write $A = A' (A')_{k-1}$, which is also of the form $A_1A_2$. Thus it suffices to explain how to compute $A_1 A_2 \land B$ (here $\land$ means AND). We will show that we can find two recursive repeating sequences $B_1B_2$ such that $B=B_1B_2$ and $|A_1|=|B_1|$, $|A_2|=|B_2|$. We can then compute $A \land B = (A_1 \land B_1) (A_2 \land B_2)$.

Given a recursive repeating sequence $B$ and a number $\ell$, we have to break $B$ into $B_1B_2$, where $|B_1| = \ell$. We consider two cases:

  1. $B = C_1 C_2 \dots C_r$. We can find $t$ such that $|C_1 C_2 \dots C_t| \leq \ell < |C_1 C_2 \dots C_t| + |C_{t+1}|$. If $|C_1 C_2 \dots C_t| = \ell$ then we can take $B_1 = C_1 C_2 \dots C_t$ and $B_2 = C_{t+1} \dots C_r$. Otherwise, we break $C_{t+1}$ into two parts $D_1D_2$, where $|D_1| = \ell - |C_1 C_2 \dots C_t|$, and take $B_1 = C_1 C_2 \dots C_t D_1$ and $B_2 = D_2 C_{t+2} \dots C_r$.

  2. $B = (C)_r$. We treat this as an explicit description of the preceding case, where $C_1 = \cdots = C_r = C$. We use division with remainder to find $t$ efficiently. In the easy case we take $B_1 = (C)_t$ and $B_2 = (C)_{r-t}$, and in the complicated case we take $B_1 = (C)_t D_1$ and $B_2 = D_2 (C)_{r-t-1}$.

  • $\begingroup$ Thank you for your answer. If I understood it correctly (notation used here): 1) |x| means the sequence length of expanded whole sequence, 2) AA means concatenated two sequences A for example, 3) lower suffix means number repetitions of sequence - correct me if I am wrong please. $\endgroup$
    – komorra
    Commented May 2, 2021 at 18:22
  • $\begingroup$ Right, that's exactly what I meant. $\endgroup$ Commented May 2, 2021 at 18:23
  • $\begingroup$ Sorry, but still I have some troubles getting it right - in some places. For example how A can be of the form A1A2 (in the second sentence of your answer)? I'm trying to imagine it but when I put for A for example 0011 - how it could be A1A2 - in this case it will state that 0011 is equal to 001100110011. Maybe A1 and A2 is just for variable suffix more here , rather than repetition? $\endgroup$
    – komorra
    Commented May 2, 2021 at 18:50
  • 1
    $\begingroup$ If $A = 0011$ then you can take $A_1 = 0$ and $A_2 = 011$. $\endgroup$ Commented May 2, 2021 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.