# Complexity of the inevitability problem over monoids

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
• 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^*$$).

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.

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$$.

• 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? Sep 5, 2023 at 8:20
• @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. Sep 5, 2023 at 8:37
• 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$. Sep 5, 2023 at 10:34
• All right, this sounds believable. Could you expand this in the answer itself? Sep 5, 2023 at 11:29
• 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
Sep 6, 2023 at 18:09