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:
- 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).
- 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.