7
$\begingroup$

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

1 Answer 1

4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.