# Are regular expressions polynomially decomposable?

This question is related to my previous question (LINK). I would like to ask whether regular expressions can be polynomially decomposed in the following sense:

A regular expression $$\mathcal{R}$$ is $$m$$-decomposable if there exist $$m$$ regular expressions $$\mathcal{R}_1, \ldots, \mathcal{R}_m$$ of size polynomial w.r.t $$\mathcal{R}$$ and a set $$\mathcal{I} \subseteq \{1,2,\ldots,m\}^2$$ such that:
• For all words $$w, v$$ and indices $$(i,j) \in \mathcal{I}$$ if $$w$$ matches $$\mathcal{R}_i$$ and $$v$$ matches $$\mathcal{R}_j$$ then $$w{\cdot}v$$ matches $$\mathcal{R}$$.
• For all words $$w$$ matching $$\mathcal{R}$$ and all their non-trivial decompositions $$w_1 w_2$$ there are indices $$(i,j) \in \mathcal{I}$$ such that $$w_1$$ matches $$\mathcal{R}_i$$ and $$w_2$$ matches $$\mathcal{R}_j$$.

My question is

Is every regular expression $$\mathcal{R}$$ $$m$$-decomposable for some $$m$$ polynomial w.r.t in $$|\mathcal{R}|$$?

I was unable to find any suitable references. Note that a similar theorem holds for NFA, where for a given NFA $$\mathcal{A}$$ it suffices to consider NFAs of the form $$\mathcal{A}_{q,q'}$$ for all states $$q,q'$$ (here $$\mathcal{A}_{q,q'}$$ denotes the automaton obtained from $$\mathcal{A}$$ by setting its initial state to $$q$$ and its final state to $$q'$$). Clearly, there are only polynomially many of them w.r.t $$|\mathcal{A}|$$ and knowing the initial and final state of $$\mathcal{A}$$ I can decide the membership in the language. Thus NFAs are "polynomially decomposable". Note also that regular expressions are "exponentially decomposable". Indeed, I can convert a regular expression into an NFA, decompose it as stated above, and then convert it into a regular expression again (the resulting regular expression is guaranteed to be at most exponential w.r.t the input automaton).

Many thanks to Florent Capelli who significantly improved my question in several ways.

• I don't think your "subsets" condition accurately captures what you want. The NFA construction you mention doesn't satisfy that condition. For instance, suppose $\mathcal{R}=(abcde)^*$. Then your NFA construction will have languages such as $\mathcal{R}_1=e(abcde)^*a$ and $\mathcal{R}_2=de(abcde)^*a$, yet $\mathcal{R}_1 \circ \mathcal{R}_2$ is not a subset of $\mathcal{R}$.
– D.W.
Dec 17, 2023 at 19:37
• Corrected. I hope that the problem statement is now finally correct. Dec 17, 2023 at 19:48
• Your NFA construction still doesn't satisfy the first of your two conditions. See my counterexample, which still shows that there is likely something wrong with the conditions stated in the question. If $w=ea \in \mathcal{R}_1$ and $v=dea \in \mathcal{R}_2$, then $w \cdot v \notin \mathcal{R}$. I don't think you've formulated the problem correctly yet.
– D.W.
Dec 17, 2023 at 20:06
• I'm afraid that I do not understand your counterexample and how the NFA construction violates the first item of the definition. Take an NFA A and let I be composed of all pairs (i,j) such that R_i is of the form A_{qinit, q'}, and R_j is of the form A_{q', qfinal}. If a word w can transform the automaton A from qinit to q', and then v can transform q' to q_final, then wv will be accepted by A. What's wrong with my understanding? Dec 17, 2023 at 20:11
• I agree with Bartosz, the fact that you can select the subset $\mathcal{I}$ makes it possible. You have prefix languages $P_q$ meaning "the word has a run from initial to $q$" and suffix languages $S_q$ meaning "the word has run from $q$ to a final state". The decomposition is $(P_q, S_q)$ for each $q$. This seems related to the communication complexity point of view but now you need to encode prefixes and suffixes in regular expressions.
– holf
Dec 18, 2023 at 10:59