Skip to main content
Theoretical Computer Science

Return to Question

deleted 28 characters in body
Source Link
Rémi
Rémi
  • 262
  • 1
  • 8

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 (and hence PSpace-complete)
  • 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 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 (and hence PSpace-complete)
  • 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 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^*$).
Source Link
Rémi
Rémi
  • 262
  • 1
  • 8

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 (and hence PSpace-complete)
  • 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^*$).