2
$\begingroup$

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 Θ(2n) exponential blow up.

One naive algorithm is recursion that computes:

enter image description here

Where:

enter image description here

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 2n nodes, thus the running time complexity of the naive recursive algorithm is Θ(2n).

Another naive algorithm is iteration that computes:

enter image description here

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 {R1, ... , Rn} and from the power set lemma it's known that {R1, ... , Rn} has 2n different subsets.

Thus the running time complexity of the naive iterative algorithm is also Θ(2n) 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 Ω(2n) 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.

$\endgroup$
  • 1
    $\begingroup$ Do I understand correctly that you consider only languages of the form $0(0+1)(0+1)1101(0+1)$, for example, you do not have an "at-most-$5$-times" operator? Asking because then all the strings are equal in length, so the problem may be easier to attack. $\endgroup$ – Lieuwe Vinkhuijzen Jul 23 '17 at 21:23
  • 1
    $\begingroup$ Computing the cardinality of the union of finite sets is called inclusion-exclusion, however wikipedia seems to offer only a nontrivial proof in generalized context. $\endgroup$ – Hendrik Jan Jul 23 '17 at 22:29
  • 1
    $\begingroup$ Your input form and size are not stated clearly (like in one of your previous question). Without knowing the exact input form it is not possible to come up with a possible algorithm and determine its complexity. How do you represent your regular expressions? Each as a single string? The structure of the strings? What operators are involved (union and concat)? A couple of examples of input would be helpful. $\endgroup$ – fade2black Jul 23 '17 at 22:57
  • $\begingroup$ I am editing my question now. $\endgroup$ – Farewell Stack Exchange Jul 23 '17 at 23:13
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So you say that the algorithm that computes the cardinality of union of sets is linear in time, because O(N) is linear, no? Of course that this question is similar to my previous one, but it is different, because now it involves regular expressions, unlike my previous question. $\endgroup$ – Farewell Stack Exchange Jul 24 '17 at 0:34
  • 1
    $\begingroup$ Yes, as long as $K$ and $M$ are fixed, but $N$ is variable. Bounded number of concatenations and word size simplify the task . $\endgroup$ – fade2black Jul 24 '17 at 0:39
  • 1
    $\begingroup$ The only difference from the previous one is that this time around you need to convert all words into integer numbers. As the set sizes and word sizes are bounded this task can be solved in $O(N)$ time, not EXPTIME. $\endgroup$ – fade2black Jul 24 '17 at 0:47
  • $\begingroup$ N is indeed variable, but K is not constant, it's also variable in the algorithm's input as N is, and M=K+1, so I afraid that the time complexity of the algorithm is O(N2^K), not O(N). $\endgroup$ – Farewell Stack Exchange Jul 24 '17 at 11:03
  • 1
    $\begingroup$ Then what does the sentence "The number of concatenations per regular expression in the sum is fixed" mean? $\endgroup$ – fade2black Jul 24 '17 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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