# DFSA and NFSA intersection problem

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?

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.

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.

• 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$.
– Mr.
Mar 13 at 23:41
• The answer is not referencing sat. So k dfa intersection in fpt has no implication to eth?
– Mr.
Mar 13 at 23:43
• @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. :) Mar 13 at 23:43
• Sorry I thought the unary case is np complete and speed up of unary case leads to eth failure. Am I wrong?
– Mr.
Mar 14 at 0:56
• @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. Mar 14 at 1:09