2
$\begingroup$

Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem.

  1. For unbounded $k$ it is known the problem is $PSPACE$ complete. What is the scale of $k$ for the problem to be PSPACE complete? Is it $k=\Omega(n)$?

  2. What is the consequence the problem is in $FPT$ having $f(k)poly(n)$ complexity for $f(k)=2^{poly(k)}$?

  3. Is there a result on intersection of deterministic DFSAs which is consistent to $CH$ is $NL$ or $L$ hypothesis (which provides $P=CH\neq PSPACE$)?

How about if the $FSA$s are all non deterministic?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Regarding question (1):

As long as $k$ is $\Omega(n^c)$ for some $c > 0$, then the problem is $PSPACE$-complete. See this paper by Klaus-Jörn Lange and Peter Rossmanith (1992) for some related results.

https://doi.org/10.1007/3-540-55808-X_33

Regarding question (2):

Say that the intersection problem is parameterized by the number of FSA's. If this parameterized problem is in $FPT$, then $PTIME \neq NLOGSPACE$.

In fact, the result is quite a bit stronger than that. Essentially, it says that if for every $\alpha > 0$, there exists $k$ sufficiently large such that the $k$th slice of the parameterized problem is solvable in $O(n^{\alpha \cdot k})$ time, then $PTIME \neq NLOGSPACE$.

See here and here.

Regarding question (3):

I am still trying to understand this question.

Regarding last question:

Both the DFA and NFA parameterized intersection problems (when parameterized by the number of automata) are fpt-equivalent. In fact, the fpt-equivalence is very strong and preserves the parameter (I called it an LBL-equivalence). Regarding your question, this implies that if one of them is in $FPT$, then the other is in $FPT$ too.

Additional information:

Part of the reason why we have these hardness results for the parameterized FSA intersection problem is because it is $XNL$-complete under a strong form of fpt-reduction. $XNL$ is a parameterized complexity class that is related to $k \cdot log(n)$ binary space nondeterministic Turing machines.

Improve this answer
$\endgroup$
32
  • 1
    $\begingroup$ 1. All these are one directional implications. Correct? 2. What is the canonical representation of the k dfa intersection problem? Are we given the grammar? Or something else? Grammar representation seems tiny compared to the number of states $n$. $\endgroup$
    – Turbo
    Mar 13, 2021 at 23:41
  • 1
    $\begingroup$ The answer is not referencing sat. So k dfa intersection in fpt has no implication to eth? $\endgroup$
    – Turbo
    Mar 13, 2021 at 23:43
  • 2
    $\begingroup$ @1.. Yes, whether you are talking about automata, grammars, or expressions, that could make a difference in the complexity. Please feel welcome to list different ways of representing regular languages and we can look at the complexity in each case. :) $\endgroup$
    – Michael Wehar
    Mar 13, 2021 at 23:43
  • 2
    $\begingroup$ Sorry I thought the unary case is np complete and speed up of unary case leads to eth failure. Am I wrong? $\endgroup$
    – Turbo
    Mar 14, 2021 at 0:56
  • 2
    $\begingroup$ @1.. Yes, the unary case is $NP$-complete and the parameterized version of the unary case is $W[1]$-complete through an fpt-equivalence with $k$-Clique. I have some slides on the $W[1]$-completeness on my website, but it is not formally published. $\endgroup$
    – Michael Wehar
    Mar 14, 2021 at 1:09

Your Answer

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

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