Complexity of bitwise AND operation on bit string regular expressions

Question

Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time of performing a bitwise AND operation on $B_1$ and $B_2$?

For example, given two regular expressions, $B_1 = ((10)^2(01)^2)^2$ and $B_2 = (01)^8$, the resulting pattern $R$ of the AND operation would be $R = ((0^4(01)^2)^2$.

Does there exist an algorithm that will run in polynomial time (with respect to the lengths of the regular expressions)? Note, you can pair every possible combination of groups in $O(n^2)$ time, where $n$ = $\max(|B_1|,|B_2|)$, and $|B_i|$ is the length of regex $B_i$. However, that still does not give you the resulting bit string regular expression $R$.

The exponent $k$ of a given substring can be stored in binary form, so it only adds $\log(k)$ bits to the representation. Furthermore, note that given any two groups of size $m$ and $n$, there are at most $\max(m,n)$ bit patterns of length $\min(m,n)$ that can result. In addition, if there are $g_1$ groups in $B_1$ and $g_2$ groups in $B_2$, then there can only be $g_1 g_2$ unique pairs of groups. Therefore, I think it can be concluded that the space required is at most $O(g_1 g_2 \max(|group_{i,B_1}|,|group_{j,B_2}|)^2)$, which is polynomial in $n$. However, I am still missing the proof that the resulting regular expression can be found in polynomial time.

For slightly easier problem, you can assume that every repetition is a power of two. However, that does not necessarily mean that groups are power of two in size. For an even further simplification you, could assume the groups are also a power of two in size.

Now that I think of it, I will include this idea which I just came up with. You can represent the offsets of the 1s every group as set of linear integer equations. Then you may be able to find solutions to pairs of integer equations with constraints somehow? Or am I over complicating it?

Another possibility is, as Yuval Filmus suggests, convert to NFA. However, I am not clear why an NFA would be needed since these are fixed sequences (that is, the number of repetitions is fixed). Furthermore, I am not sure how one would apply the AND operation after they are in NFA form.

Answer 1

Formalism

Let me formalize your problem as follow. Define a gegular expression as an expression that follows the following grammar:

$$E ::= 0 | 1 | E_1 E_2 | E^k,$$

where $k$ ranges over positive integers and $E_1,E_2$ range over gegular expressions. Note that these are not regular expressions, as Yuval Filmus explains, even though they are related.

Obviously, each gegular expression codes for a single binary string. If $E$ is a gegular expression, let $[E]$ be the binary string is codes for. Also let $\text{len}(E)=\text{len}([E])$ denote the length of the binary string $[E]$. Of course, these can be easily computed recursively: e.g., $\text{len}(E_1 E_2) = \text{len}(E_1) + \text{len}(E_2)$ and $\text{len}(E^k) = k \times \text{len}(E)$.

Given two gegular expressions $E_1,E_2$, the ultimate goal is to find a third gegular expression $E_3$ such that

$$[E_3] = [E_1] \land [E_2],$$

i.e., that represents the bitwise-AND of the bit strings that $E_1,E_2$ code for. If this holds, we will write $E_3 = E_1 \land E_2$. ($E_3$ may not be unique -- there may be multiple acceptable $E_3$ -- but we won't let this bother us.)

Helpful tools

Here are some little lemmas that are helpful.

First, if $E$ is a gegular expression and $\ell$ is a positive integer, we can compute a new gegular expression that codes for the first $\ell$ bits of $[E]$. Define $\text{prefix}_\ell(E)$ to be this gegular expression. We can compute $\text{prefix}_\ell(E)$ recursively using the following relations:

$$\text{prefix}_\ell(E_1 E_2) = \begin{cases} \text{prefix}_\ell(E_1) &\text{if $\ell < \text{len}(E_1)$}\\ E_1 &\text{if $\ell = \text{len}(E_1)$}\\ E_1 \; \text{prefix}_{\ell-\text{len}(E_1)}(E_2) &\text{otherwise.} \end{cases}$$

$$\text{prefix}_\ell(E^k) = E^{\lfloor \ell / \text{len}(E) \rfloor} \; \text{prefix}_{\ell \bmod \text{len}(E)}(E).$$

You might notice that this does not increase the size of the gegular expression too much (at most a quadratic blowup, and usually much less).

Also, there are some special cases where your problem is easy. For instance.

$$E_1^k \land E_2^k = (E_1 \land E_2)^k$$

if $\text{len}(E_1)=\text{len}(E_2)$.

If the exponents are not identical, we can reduce to the above case. Let $E_1,E_2$ be two gegular expressions of lengths $\ell_1,\ell_2$, respectively (i.e., $\ell_i = \text{len}(E_i)$). Let $m = \text{lcm}(\ell_1,\ell_2)$ be the least common multiple of their lengths. Then

$$E^k = (E E \cdots E)^{\lfloor k/m \rfloor} E E \cdots E$$

holds for all $E,k,m$, where the first $E E \cdots E$ represents $m$ concatenations of $E$ and the second $E E \cdots E$ represents $k \bmod m$ concatenations. Thus we have

$$E_1^{k_1} \land E_2^{k_2} = (E_1 E_1 \cdots E_1 \land E_2 E_2 \cdots E_2)^{k_3} \; \big( \text{prefix}_{\ell'_1}(E_1^{k_1}) \land \text{prefix}_{\ell'_2}(E_2^{k_2}) \big),$$

Also, if $\text{len}(E_1) = \text{len}(E'_1)$, then

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land E'_1) (E_2 \land E'_2).$$

If they are not of the same length, say $E_1,E'_1$ have lengths $\ell_1,\ell_2$ where $\ell_1<\ell_2$, then we can express their bitwise-AND as

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land \text{prefix}_{\ell_1}(E'_1)) (\text{prefix}_{\ell_2-\ell_1}(E_2) \land \text{tail}_{\ell_2-\ell_1}(E'_1)) (\text{tail}_{\text{len}(E'_2)}(E_2) \land E'_2).$$

(Here $\text{tail}()$ is defined analogously to $\text{prefix}()$, except it relates to the end of a string rather than the beginning.)

I think from these special cases, you should be able to build a recursive algorithm that computes the bitwise-AND of any two gegular expressions.