How to perform AND on binary "recursive repeating sequences"?

Question

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:

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.

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}$.