<p>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 <a href="https://cstheory.stackexchange.com/questions/53654/the-complexity-of-conversion-from-a-regular-expression-to-a-nondeterminsitic-aut">POST</a>.</p>

CC BY-SA 4.0
2023-12-22T13:49:41.827Z
2023-12-22T13:49:41.827Z
Bartosz Bednarczyk
<p>This question is related to my previous question (<a href="https://cstheory.stackexchange.com/questions/53654/the-complexity-of-conversion-from-a-regular-expression-to-a-nondeterminsitic-aut">LINK</a>).
I would like to ask whether regular expressions can be polynomially decomposed in the following sense:</p>
<blockquote>
A regular expression <span class="math-container">$\mathcal{R}$</span> is <span class="math-container">$m$</span>-decomposable if there exist <span class="math-container">$m$</span> regular expressions <span class="math-container">$\mathcal{R}_1, \ldots, \mathcal{R}_m$</span> of size polynomial w.r.t <span class="math-container">$\mathcal{R}$</span> and a set <span class="math-container">$\mathcal{I} \subseteq \{1,2,\ldots,m\}^2$</span> such that:
<ul>
<li>For all words <span class="math-container">$w, v$</span> and indices <span class="math-container">$(i,j) \in \mathcal{I}$</span> if <span class="math-container">$w$</span> matches <span class="math-container">$\mathcal{R}_i$</span> and <span class="math-container">$v$</span> matches <span class="math-container">$\mathcal{R}_j$</span> then <span class="math-container">$w{\cdot}v$</span> matches <span class="math-container">$\mathcal{R}$</span>.</li>
<li>For all words <span class="math-container">$w$</span> matching <span class="math-container">$\mathcal{R}$</span> and all their non-trivial decompositions <span class="math-container">$w_1 w_2$</span> there are indices <span class="math-container">$(i,j) \in \mathcal{I}$</span> such that <span class="math-container">$w_1$</span> matches <span class="math-container">$\mathcal{R}_i$</span> and <span class="math-container">$w_2$</span> matches <span class="math-container">$\mathcal{R}_j$</span>.</li>
</ul>
</blockquote>
<p>My question is</p>
<blockquote>
Is every regular expression <span class="math-container">$\mathcal{R}$</span> <span class="math-container">$m$</span>-decomposable for some <span class="math-container">$m$</span> polynomial w.r.t in <span class="math-container">$|\mathcal{R}|$</span>?
</blockquote>
<p>I was unable to find any suitable references.
Note that a similar theorem holds for NFA, where for a given NFA <span class="math-container">$\mathcal{A}$</span> it suffices to consider  NFAs of the form <span class="math-container">$\mathcal{A}_{q,q'}$</span> for all states <span class="math-container">$q,q'$</span> (here <span class="math-container">$\mathcal{A}_{q,q'}$</span> denotes the automaton obtained from <span class="math-container">$\mathcal{A}$</span> by setting its initial state to <span class="math-container">$q$</span> and its final state to <span class="math-container">$q'$</span>). Clearly, there are only polynomially many of them w.r.t <span class="math-container">$|\mathcal{A}|$</span> and knowing the initial and final state of <span class="math-container">$\mathcal{A}$</span> I can decide the membership in the language. Thus NFAs are &quot;polynomially decomposable&quot;.
Note also that regular expressions are &quot;exponentially decomposable&quot;. 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).</p>
<p>Many thanks to Florent Capelli who significantly improved my question in several ways.</p>

CC BY-SA 4.0
2023-12-17T19:37:03.707Z
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.
CC BY-SA 4.0
2023-12-17T19:48:12.703Z
Corrected. I hope that the problem statement is now finally correct.
Bartosz Bednarczyk
CC BY-SA 4.0
2023-12-17T20:06:32.063Z
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.
CC BY-SA 4.0
2023-12-17T20:11:06.483Z
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?
Bartosz Bednarczyk
CC BY-SA 4.0
2023-12-18T10:59:14.810Z
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
<automata-theory><regular-language><regular-expressions><nfa>
Are regular expressions polynomially decomposable?
Bartosz Bednarczyk
# Are regular expressions polynomially decomposable?

(Asked by: username_0 on 2023-12-17)

This question is related to my previous question ([LINK](https://cstheory.stackexchange.com/questions/53654/the-complexity-of-conversion-from-a-regular-expression-to-a-nondeterminsitic-aut)).
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.

**Tags:** automata-theory, regular-language, regular-expressions, nfa

> **Comments:**
> **username_1**: 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}$.  
> **username_0**: Corrected. I hope that the problem statement is now finally correct.  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_0 on 2023-12-22. Score: 2 | Accepted answer

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](https://cstheory.stackexchange.com/questions/53654/the-complexity-of-conversion-from-a-regular-expression-to-a-nondeterminsitic-aut).


---

