Implication of regular expressions

In this work we study the following implication problem for regular expressions: “Given a set of regular expressions R and a regular expression SS, is it true that every string which matches the regular expressions in R also matches SS?” The problem comes in two flavors: “non-disjoint” and “disjoint”. We show that both of them are PSPACE-complete. While the complexity for the first variant is not surprising–the problem is coNP-complete even for very simple patterns (given by wildcards)–the complexity result for the second variant represents a big jump since the problem is in PTIME for the case of patterns with wildcards. Towards the goal of charting the boundary of tractability, we then present an analysis of when the problem remains in PTIME.