<p>I think it is PSpace-complete, here is a proof scheme.</p>
<p>We can go back to the proof scheme for PSpace-completeness of regular expression universality, e.g. described in <a href="https://cstheory.stackexchange.com/questions/40247/parameterized-complexity-of-inclusion-of-regular-languages/40250#40250">this answer</a>.</p>
<p>There we can see that the reduction uses a disjunction of expressions <span class="math-container">$e_0, e_1,e_2,\dots,e_k$</span>, where most expressions <span class="math-container">$e_i$</span> are of the form <span class="math-container">$\Sigma^* f_i \Sigma^*$</span>, where <span class="math-container">$f_i$</span> describes a fixed-sized infix, that is a forbidden pattern in a run of the PSpace machine <span class="math-container">$M$</span>. The exceptions to this are the expressions stating that the prefix does not describe an initial configuration, and about the suffix not describing a final configuration, assume these are <span class="math-container">$e_0$</span> and <span class="math-container">$e_k$</span>.</p>
<p>Let us take <span class="math-container">$L=f_1+f_2+\dots+f_{k-1}$</span>, and <span class="math-container">$K$</span> the language stating that the word starts with an initial configuration and ends with a final one.</p>
<p>We have <span class="math-container">$K\subseteq \Sigma^*L\Sigma^*$</span> if and only if the PSpace machine <span class="math-container">$M$</span> does not halt. Indeed this inclusion expresses the fact that any word describing a run that starts with an initial configuration and ends with a final one must &quot;cheat&quot; somewhere.</p>
<p>The only thing that remains to be carefully verified is that the monoids of <span class="math-container">$L$</span> and <span class="math-container">$K$</span> are of polynomial size, but it seems to be the case.</p>
<p>Notice that for some expressions, you can either put them in <span class="math-container">$L$</span> or put their complement in <span class="math-container">$K$</span>, for instance the constraint that in any run you must have exactly one state between any two <span class="math-container">$\$$</span>. It can either be formulated as a polynomial forbidden pattern everywhere (for <span class="math-container">$L$</span>), or by a language that you can describe with a small monoid (for <span class="math-container">$K$</span>).</p>
<p>Bottomline, the intuition is that the main source of nondeterminism that causes the PSpace-hardness of regular expression universality, is the one encoded by expressions of the form <span class="math-container">$\Sigma^*f\Sigma^*$</span>, i.e. the ability to search for a pattern anywhere in the word.</p>
<hr />
<p>Added from the comments: more precisions on why we can obtain a polynomial-sized monoid for <span class="math-container">$L$</span>:</p>
<p>The typical job of the syntactic monoid of <span class="math-container">$L$</span> will be to recognize a union of languages of the form <span class="math-container">$p_1\Sigma^*p_2$</span>, where <span class="math-container">$p_1$</span> and <span class="math-container">$p_2$</span> are small patterns (say of <span class="math-container">$3$</span> letters). It is doable with a polynomial size monoid, which just remembers the length of the word and the <span class="math-container">$3$</span>-letter words on the sides.</p>
<p>You could restrict a lot of the variation in <span class="math-container">$L$</span>, by choosing for <span class="math-container">$M$</span> a universal Turing machine <span class="math-container">$M_u$</span> (with polynomial simulation overhead). This way, the number of forbidden local patterns will be a constant, as it will only depend on the transition table of <span class="math-container">$M_u$</span>, and the only variation in <span class="math-container">$L$</span> will be the length <span class="math-container">$n$</span> of configurations. The arbitrary PSpace problem will be fully encoded in the initial configuration of the tape, itself encoded in <span class="math-container">$K$</span>.</p>

CC BY-SA 4.0
2023-09-05T08:20:17.763Z
It sounds rather non-obvious to me that the syntactic monoids are of polynomial size. For example, why does the syntactic monoid of $L$ not encode the set of forbidden patterns violated by the current word?
Emil Jeřábek
CC BY-SA 4.0
2023-09-05T08:37:59.420Z
@EmilJeřábek The typical job of the syntactic monoid of $L$ will be to recognize a union of languages of the form $p_1\Sigma^n p_2$, where $p_1$ and $p_2$ are small patterns (say of 3 letters). It is doable with a polynomial size monoid, which just remembers the length of the word and the 3-letter words on the sides.
Denis
CC BY-SA 4.0
2023-09-05T10:34:40.030Z
You could even restrict even more the variation in $L$, by choosing for $M$ a universal Turing machine $M_u$ (with polynomial simulation overhead). This way, the number of forbidden local patterns will be a constant, as it will only depend on the transition table of $M_u$, and the only variation in $L$ will be the length $n$ of configurations. The arbitrary PSpace-complete problem will be fully encoded in the initial configuration of the tape, itself encoded in $K$.
Denis
CC BY-SA 4.0
2023-09-05T11:29:01.287Z
All right, this sounds believable. Could you expand this in the answer itself?
Emil Jeřábek
CC BY-SA 4.0
2023-09-05T11:54:49.610Z
the comments are added in the answer
Denis
CC BY-SA 4.0
2023-09-06T18:09:33.163Z
Thanks! Based on your answer, I think you can also show PSpace-hardness by reducing from the PSpace tiling problem (it's exactly the same idea as your reduction). Given a set of tiles, horizontal contraints, vertical constraints, an initial and a final tile, and a width $n$, take $K$ to be the set of sequences of tiles, whose length is a multiple of $n$, whose first tile is the initial one and one last tile is the final one. Take $L$ as the union of languages of the form $st$ [resp. $s\Sigma^{n-1} t$] where $(s,t)$ is a pair of horizontally [resp. vertically] non-compatible tiles.
Rémi
CC BY-SA 4.0
2023-09-06T21:20:30.963Z
@Rémi indeed it's simpler and gets rid of some of the encoding bookkeeping
Denis
CC BY-SA 4.0
2023-09-04T21:45:02.733Z
2023-09-05T11:59:09.297Z
2023-09-05T11:59:09.297Z
Denis
<p>I am interested in the complexity of following problem:</p>
<blockquote>
<p><strong>Inevitability problem in monoids</strong></p>
<p>Input: two regular languages <span class="math-container">$K$</span>, <span class="math-container">$L$</span> specified by finite monoids <span class="math-container">$M_K$</span> and <span class="math-container">$M_L$</span> (+ morphisms and accepting sets)</p>
<p>Question: Does <span class="math-container">$K \subseteq \Sigma^*L\Sigma^*$</span>?</p>
</blockquote>
<p><strong>Question:</strong> What is the complexity of the inevitability problem in monoids? Is it PSpace-complete?</p>
<p>Here is what I know:</p>
<ul>
<li>the problem is NL-hard,</li>
<li>the problem is in PSpace (this follows from the fact that the size of a minimal counter-example to <span class="math-container">$K \subseteq \Sigma^*L\Sigma^*$</span> has size at most <span class="math-container">$|M_K|\cdot2^{|M_L|}$</span>),</li>
<li>the size of the syntactic monoid for <span class="math-container">$\Sigma^*L\Sigma^*$</span> can be exponential in the size of the syntactic monoid for <span class="math-container">$L$</span>: for instance, take <span class="math-container">$L = a\Sigma^n a$</span> for <span class="math-container">$\Sigma = \{a,b\}$</span></li>
<li>the problem <span class="math-container">$K \subseteq^? L\Sigma^*$</span> is NL (more generally this holds for languages specified by deterministic automata)</li>
<li>the problem <span class="math-container">$K \subseteq^? \Sigma^*L$</span> is NL (more generally this holds for languages specified by co-deterministic automata)</li>
<li>the intersection non-emptiness problem for monoids is PSpace-complete by <a href="https://drops.dagstuhl.de/opus/volltexte/2018/8507/" rel="nofollow noreferrer">Fleischer-Kufleitner '18, Theorem 11</a></li>
<li>as a consequence of the previous item, <span class="math-container">$K \subseteq^? \bigcup_i \Sigma^* L_i \Sigma^*$</span> is PSpace-hard</li>
<li>the problem would be PSpace-hard if specified by non-deterministic automata, by reduction from the universality problem (reduce <span class="math-container">$\Sigma^* =^? L$</span> to <span class="math-container">$\$\Sigma^*\$ \subseteq^? \Sigma^*\$L\$\Sigma^*$</span>).</li>
</ul>

<fl.formal-languages><automata-theory><regular-language><monoid>
Complexity of the inevitability problem over monoids
Rémi
# Complexity of the inevitability problem over monoids

(Asked by: username_0 on 2023-08-31)

I am interested in the complexity of following problem:

> **Inevitability problem in monoids**
>
> Input: two regular languages $K$, $L$ specified by finite monoids $M\_K$ and $M\_L$ (+ morphisms and accepting sets)
>
> Question: Does $K \subseteq \Sigma^\*L\Sigma^\*$?

**Question:** What is the complexity of the inevitability problem in monoids? Is it PSpace-complete?

Here is what I know:

* the problem is NL-hard,
* the problem is in PSpace (this follows from the fact that the size of a minimal counter-example to $K \subseteq \Sigma^\*L\Sigma^\*$ has size at most $|M\_K|\cdot2^{|M\_L|}$),
* the size of the syntactic monoid for $\Sigma^\*L\Sigma^\*$ can be exponential in the size of the syntactic monoid for $L$: for instance, take $L = a\Sigma^n a$ for $\Sigma = \{a,b\}$
* the problem $K \subseteq^? L\Sigma^\*$ is NL (more generally this holds for languages specified by deterministic automata)
* the problem $K \subseteq^? \Sigma^\*L$ is NL (more generally this holds for languages specified by co-deterministic automata)
* the intersection non-emptiness problem for monoids is PSpace-complete by [Fleischer-Kufleitner '18, Theorem 11](https://drops.dagstuhl.de/opus/volltexte/2018/8507/)
* as a consequence of the previous item, $K \subseteq^? \bigcup\_i \Sigma^\* L\_i \Sigma^\*$ is PSpace-hard
* the problem would be PSpace-hard if specified by non-deterministic automata, by reduction from the universality problem (reduce $\Sigma^\* =^? L$ to $\$\Sigma^\*\$ \subseteq^? \Sigma^\*\$L\$\Sigma^\*$).

**Tags:** fl.formal-languages, automata-theory, regular-language, monoid

---

## 1 answers

### Answer by username_1 on 2023-09-04. Score: 4 | Accepted answer

I think it is PSpace-complete, here is a proof scheme.

We can go back to the proof scheme for PSpace-completeness of regular expression universality, e.g. described in [this answer](https://cstheory.stackexchange.com/questions/40247/parameterized-complexity-of-inclusion-of-regular-languages/40250#40250).

There we can see that the reduction uses a disjunction of expressions $e\_0, e\_1,e\_2,\dots,e\_k$, where most expressions $e\_i$ are of the form $\Sigma^\* f\_i \Sigma^\*$, where $f\_i$ describes a fixed-sized infix, that is a forbidden pattern in a run of the PSpace machine $M$. The exceptions to this are the expressions stating that the prefix does not describe an initial configuration, and about the suffix not describing a final configuration, assume these are $e\_0$ and $e\_k$.

Let us take $L=f\_1+f\_2+\dots+f\_{k-1}$, and $K$ the language stating that the word starts with an initial configuration and ends with a final one.

We have $K\subseteq \Sigma^\*L\Sigma^\*$ if and only if the PSpace machine $M$ does not halt. Indeed this inclusion expresses the fact that any word describing a run that starts with an initial configuration and ends with a final one must "cheat" somewhere.

The only thing that remains to be carefully verified is that the monoids of $L$ and $K$ are of polynomial size, but it seems to be the case.

Notice that for some expressions, you can either put them in $L$ or put their complement in $K$, for instance the constraint that in any run you must have exactly one state between any two $\$$. It can either be formulated as a polynomial forbidden pattern everywhere (for $L$), or by a language that you can describe with a small monoid (for $K$).

Bottomline, the intuition is that the main source of nondeterminism that causes the PSpace-hardness of regular expression universality, is the one encoded by expressions of the form $\Sigma^\*f\Sigma^\*$, i.e. the ability to search for a pattern anywhere in the word.

---

Added from the comments: more precisions on why we can obtain a polynomial-sized monoid for $L$:

The typical job of the syntactic monoid of $L$ will be to recognize a union of languages of the form $p\_1\Sigma^\*p\_2$, where $p\_1$ and $p\_2$ are small patterns (say of $3$ letters). It is doable with a polynomial size monoid, which just remembers the length of the word and the $3$-letter words on the sides.

You could restrict a lot of the variation in $L$, by choosing for $M$ a universal Turing machine $M\_u$ (with polynomial simulation overhead). This way, the number of forbidden local patterns will be a constant, as it will only depend on the transition table of $M\_u$, and the only variation in $L$ will be the length $n$ of configurations. The arbitrary PSpace problem will be fully encoded in the initial configuration of the tape, itself encoded in $K$.

> **Comments:**
> **username_2**: It sounds rather non-obvious to me that the syntactic monoids are of polynomial size. For example, why does the syntactic monoid of $L$ not encode the set of forbidden patterns violated by the current word?  
> **username_1**: @EmilJeřábek The typical job of the syntactic monoid of $L$ will be to recognize a union of languages of the form $p_1\Sigma^n p_2$, where $p_1$ and $p_2$ are small patterns (say of 3 letters). It is doable with a polynomial size monoid, which just remembers the length of the word and the 3-letter words on the sides.  
> **username_1**: You could even restrict even more the variation in $L$, by choosing for $M$ a universal Turing machine $M_u$ (with polynomial simulation overhead). This way, the number of forbidden local patterns will be a constant, as it will only depend on the transition table of $M_u$, and the only variation in $L$ will be the length $n$ of configurations. The arbitrary PSpace-complete problem will be fully encoded in the initial configuration of the tape, itself encoded in $K$.  
> **username_2**: All right, this sounds believable. Could you expand this in the answer itself?  
> **username_1**: the comments are added in the answer  
> **username_0**: Thanks! Based on your answer, I think you can also show PSpace-hardness by reducing from the PSpace tiling problem (it's exactly the same idea as your reduction). Given a set of tiles, horizontal contraints, vertical constraints, an initial and a final tile, and a width $n$, take $K$ to be the set of sequences of tiles, whose length is a multiple of $n$, whose first tile is the initial one and one last tile is the final one. Take $L$ as the union of languages of the form $st$ [resp. $s\Sigma^{n-1} t$] where $(s,t)$ is a pair of horizontally [resp. vertically] non-compatible tiles.  
> **username_1**: @Rémi indeed it's simpler and gets rid of some of the encoding bookkeeping  

---

