Is computing the cardinality of sum of regular expressions without kleene star closure EXPTIME problem?

Question

Is computing the cardinality of sum of regular expressions without kleene star closure is EXPTIME problem?

Note that sum of regular expressions is union of regular expressions. The alphabet of each regular expression is Σ={0,1}, and each regular expression in the sum is concatenation of 0, 1 and (0+1).

There is no kleene star closure, so the regular language of the sum of regular expressions is finite, and so the cardinality of this regular language is finite natural number, as defined in discrete mathematics, which is the number of words in this regular language.

There are two known naive algorithms to compute this, but their running time are both Θ(2ⁿ) exponential blow up.

One naive algorithm is recursion that computes:

Where:

Computing the intersection regular language of two regular languages should be easy, because the fact that each regular expression in the sum is just concatenation of 0, 1 and (0+1), so in parallel 0∩0=0, 1∩1=1, (0+1)∩(0+1)=(0+1), 0∩(0+1)=0, 1∩(0+1)=1 and if 0 is found in regexp A and 1 in regexp B at the same offset or 1 is found in regexp A and 0 in regexp B at the same offset then L(A)∩L(B)=∅, i.e. both the languages are disjoint.

But the naive recursive algorithm runs over complete binary tree, whose height is n and it has 2ⁿ nodes, thus the running time complexity of the naive recursive algorithm is Θ(2ⁿ).

Another naive algorithm is iteration that computes:

The general formula was taken from this proof wiki webpage that doesn't show any proof for this formula.

But it seems that the algorithm iterates over all the different subsets of {R₁, ... , R_n} and from the power set lemma it's known that {R₁, ... , R_n} has 2ⁿ different subsets.

Thus the running time complexity of the naive iterative algorithm is also Θ(2ⁿ) exponential blow up as well as the naive recursive algorithm.

All known algorithms for this problem, for me, are exponential run time and thus it seems that this problem is EXPTIME, according to the definition of EXPTIME in computational complexity theory.

Maybe all best algorithms for this problem are Ω(2ⁿ) exponential run time, and there is no polynomial run time algorithm to compute this, but this requires a proof.

Just finding 2 exponential run time algorithms is not a proof.

But I don't know if this question is open or not in computer science.

I tried to google the answer for hours, but I didn't find it yet.

Is this open question in computer science?

If not, then what is the proof that this problem is in P or not in P, i.e. does exist polynomial algorithm to solve this problem?

EDIT:

Algorithm's input is sum of regular expressions, where each regular expression is concatenation of 0, 1 and (0+1).

The number of concatenations per regular expression in the sum is fixed.

All words in the regular language of the sum of regular expressions are in the same length.

The only operators in the regular expression are sum and concatenation.

EDIT:

"The number of concatenations per regular expresion in the sum is fixed."

infers the length of each word in the regular language.

If there is 1 concatenation, then the length of each word is 2, if there are 2 concatenations then the length of each word 3, if there are k concatenations then the length of each word is k+1.

For example in the regular expression: 0(0+1)1, there are 2 concatenations:

first concatenation is between 0 and (0+1) and second concatenation is between (0+1) and 1, so in total there are 2 concatenations and thus the length of each word in the regular language is 3, because all the other regular expressions in the sum have the same number of concatenations, in this example they all have 2 concatenations.

There are 2 words in the example regular expression above: 001 and 011, and their length is 3, and you can see that number of concatenations between each two nearby characters is 2.

Either number of concatenations per regular expression or the length of each word in the regular language is given in the algorithm's input. This is not necessary that both are given, because if one of them is given, then this is possible to infer the other due to their relationship.

Answer 1

Assume that each of your regular expressions has only parentheses, + as union, and a concatenation operator. For example $$01(01 + 1)$$ $$(01 + 1)011+01$$ are possible inputs. Since each regular expression represents a finite set of strings over $0$ and $1$, first you could rewrite them as a finite sets of strings. For example $01(01 + 1)$ is equivalent to $0101 + 011$, simply multiply by getting rid of parentheses. If the number of concatenations is fixed, say $K$, then the upper bound for transformation (or expansion) is $2^K$ corresponding to the following input $$(0+1)(0+1)\dots (0+1) \ \ \ \ \ (K \text{ times})$$ This string generates $2^K$ different words. Thus if the number of regular expressions $N$ which constitutes the input size and $K$ is fixed then $2^K$ may be considered as constant w.r.t $N$. So the transformation of all regular expressions into the set of words takes $N2^K$ time which is $O(N)$.

Now, in fact each word is the binary representation of an integer, so you could treat them as sets of integers. And since each word is bound as well, say at most of the length $M$ (also fixed!), then you have at most $2^M$ integers which can be stored in the array of size $2^M$ (if not too large) or as bitmap and accessed in $O(1)$ time.

Thus to compute the cardinality of union of these sets you simply count the number of different elements in all sets/arrays - D.W. has already answered here. That shouldn't take more that $O(N)$ either.