Are regular expressions polynomially decomposable?

Question

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.

Answer 1

The answer to my question turned out to be positive, which follows from a translation from regular expressions to automata and back. Check the answer of Hermann Gruber to my previous POST.