DFA to regular expression time complexity

Question

I am looking at the time complexity analysis of converting DFAs to regular expressions in the "Introduction to the Automata Theory, Languages and Computation", 2nd edition, page 151, by Ullman et al. This method is sometimes referred to as the transitive closure method. I don't understand how they came up with the 4^n expression in the O((n^3)*(4^n)) time complexity.

I understand that the 4^n expression holds regarding space complexity, but, regarding time complexity, it seems that we are performing only four constant time operations for each pair of states at each iteration, using the results of the previous iterations. What am I exactly missing?

Answer 1

It's a crude bound on the complexity of an algorithm that isn't using the right data structures. I don't think that there's much to explain other than that the authors clearly did not care to optimize here, probably because their main point was that regular expressions are at least as expressive as DFAs and because they feel that it's pointless to optimize this exponential-time algorithm.

There are three nested loops of n iterations each; the regular expressions constructed during iteration k of the outer loop inductively have size O(4^k), since they are constructed from at most four regular expressions constructed during the previous iteration. If the algorithm copies these subexpressions and we overestimate the regular-expression size bound at O(4^n) for all iterations, then we get O(n^3 4^n).

Obviously we can do better. Without eliminating the copying, we can get O(sum_{k=1}^n n^2 4^k) = O(n^2 (n + 4^n)) by bounding the geometric sum properly. Moreover, as you point out, we don't need to copy at all, except at the end if we agree with templatetypedef that the output must be completely written out, giving a running time of O(n^3) to prepare the regular expression and O(4^n) to write it out. The space complexity for this version equals the time complexity.

Answer 2

I suppose your doubt is about the n³ Time Complexity.

Let us assume R_ij^k represents the set of all strings that transition the automata from state q_i to q_j without passing through any state higher than q_k.

Then the iterative formula for R_ij^k is shown below,

R_ij^k = R_ik^k-1 (R_kk^k-1)^* R_kj^k-1 + R_ij^k-1.

This technique is similar to the all-pairs shortest path problem. The only difference is that we are taking the union and concatenation of regular expressions instead of summing up distances. The Time Complexity of all-pairs shortest path problem is n³. So we can expect the same complexity for DFA to Regular Expression Conversion also. The same method can also be used to convert NFA and ε-NFA to corresponding Regular Expressions.

The main problem of transitive closure approach is that it creates very large regular expressions. This large length is due to the repeated union of concatenated terms.