<p><strong>Regarding question (1):</strong></p>
<p>As long as <span class="math-container">$k$</span> is <span class="math-container">$\Omega(n^c)$</span> for some <span class="math-container">$c &gt; 0$</span>, then the problem is <span class="math-container">$PSPACE$</span>-complete.  See this paper by Klaus-Jörn Lange and Peter Rossmanith (1992) for some related results.</p>
<p><a href="https://doi.org/10.1007/3-540-55808-X_33" rel="nofollow noreferrer">https://doi.org/10.1007/3-540-55808-X_33</a></p>
<p><strong>Regarding question (2):</strong></p>
<p>Say that the intersection problem is parameterized by the number of FSA's.  If this parameterized problem is in <span class="math-container">$FPT$</span>, then <span class="math-container">$PTIME \neq NLOGSPACE$</span>.</p>
<p>In fact, the result is quite a bit stronger than that.  Essentially, it says that if for every <span class="math-container">$\alpha &gt; 0$</span>, there exists <span class="math-container">$k$</span> sufficiently large such that the <span class="math-container">$k$</span>th slice of the parameterized problem is solvable in <span class="math-container">$O(n^{\alpha \cdot k})$</span> time, then <span class="math-container">$PTIME \neq NLOGSPACE$</span>.</p>
<p>See <a href="http://michaelwehar.com/IntersectionNonEmptiness.html" rel="nofollow noreferrer">here</a> and <a href="http://michaelwehar.com/documents/mwehar_dissertation.pdf" rel="nofollow noreferrer">here</a>.</p>
<p><strong>Regarding question (3):</strong></p>
<p>I am still trying to understand this question.</p>
<p><strong>Regarding last question:</strong></p>
<p>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 <span class="math-container">$FPT$</span>, then the other is in <span class="math-container">$FPT$</span> too.</p>
<p><strong>Additional information:</strong></p>
<p>Part of the reason why we have these hardness results for the parameterized FSA intersection problem is because it is <span class="math-container">$XNL$</span>-complete under a strong form of fpt-reduction.  <span class="math-container">$XNL$</span> is a parameterized complexity class that is related to <span class="math-container">$k \cdot log(n)$</span> binary space nondeterministic Turing machines.</p>

CC BY-SA 4.0
2021-03-13T23:41:17.270Z
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$.
Turbo
CC BY-SA 4.0
2021-03-13T23:43:17.090Z
The answer is not referencing sat. So k dfa intersection in fpt has no implication to eth?
Turbo
CC BY-SA 4.0
2021-03-13T23:43:31.003Z
@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.  :)
Michael Wehar
CC BY-SA 4.0
2021-03-13T23:45:05.600Z
@1.. In this paper we looked at the implications regarding ETH, SETH, and circuit lower bounds: https://doi.org/10.1007/978-3-030-48516-0_6
Michael Wehar
CC BY-SA 4.0
2021-03-13T23:45:45.833Z
@1.. Wow, you ask a lot of questions that I am interested in.  We should chat sometime.  :)
Michael Wehar
CC BY-SA 4.0
2021-03-13T23:57:20.653Z
1. What representation do you assume in your answers? 2. So there is no speed up of sat beyond measly falsification of Seth assuming k dfa intersection is in $quasipoly(nk)$?
Turbo
CC BY-SA 4.0
2021-03-14T00:06:27.190Z
@1.. I generally represent the FSA's (approximately) as directed labeled graphs.  What parameters you are measuring runtime in terms of and how you encode the input can result in some slight differences.
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:12:52.373Z
@1.. There are some results by Fernau and Krebs regarding breaking ETH.  See here: https://doi.org/10.3390/a10010024
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:16:17.547Z
Qptime seems to be something I am thinking as an assumption. Let me think.
Turbo
CC BY-SA 4.0
2021-03-14T00:20:39.473Z
@1.. Also, in my 2014 paper that I mentioned, one of my reductions (see Theorem 7) shows that the problem is still $PSPACE$-complete even for $n$ many FSA's with $O(log(n))$ states each.  In other words, if the FSA intersection problem is in $quasipoly(n \cdot k)$ time, then that should imply that $NSPACE(n) \subseteq QPTIME$.
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:21:19.373Z
So you represent fsa as -1/0/1 poly(n) sized adjacency matrices?
Turbo
CC BY-SA 4.0
2021-03-14T00:22:37.673Z
@1.. Adjacency matrices (or adjacency lists) plus information about start and accept states.
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:24:29.187Z
@1.. How did you start investigating this problem?  I would be interested to hear more about your research direction.  :)
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:25:09.067Z
Is there a graph theoretic statement of k dsa intersection problem? Like all graphs have an isomorphic path from start to accept state?
Turbo
CC BY-SA 4.0
2021-03-14T00:27:19.117Z
I am thinking of what would be implications if we allow at most $j$ of the dsa have intersection. Counting, mod_k versions, randomized versions etc of  at most $j$ intersections. These results are not yet in counting frameworks. Path theoretic framework would be helpful. So is there a path theoretic framework?
Turbo
CC BY-SA 4.0
2021-03-14T00:29:16.717Z
@1.. Actually, there are multiple algebraic problems that are related or equivalent.  You might want to look at the works by Lukas Fleischer and Michael Blondin on this problem.
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:32:22.527Z
Do they have a path theoretic framework?
Turbo
CC BY-SA 4.0
2021-03-14T00:33:24.427Z
@1.. I am trying to figure out what that means.  Could you possibly give some example problems to demonstrate what you mean by path theoretic framework?  Also, I think you are onto something regarding question (3).  I still need to think about this a bit.
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:36:30.160Z
Start state and end states are vertices in graph. A  string is in L iff there is a path from start to end states.
Turbo
CC BY-SA 4.0
2021-03-14T00:37:37.917Z
@1.. Yes, the classic algorithm is to determine whether there exists a path from a product start state to a product final state in the product automaton's state diagram.  But, this has runtime roughly $O(n^k)$.
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:39:06.283Z
If you want to continue this discussion outside of stackexchange, please feel welcome to email me.  We could even set up a time to Zoom if you like.  Otherwise, you can continue commenting here.  :)
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:48:26.697Z
I think it is surprising there is no statement similar to eth fails implies we can speed up k dsa intersection problem. Such a statement would demonstrate eth fails iff k dsa is in faster time and so eth fails implies p not nl.
Turbo
CC BY-SA 4.0
2021-03-14T00:54:17.503Z
@1.. My initial reaction is that $SAT$ is $NP$-complete and FSA intersection if $PSPACE$-complete so reductions from FSA intersection to $SAT$ are tricky to find because $NP$ vs $PSPACE$ hasn't been solved yet.
Michael Wehar
CC BY-SA 4.0
2021-03-14T00:56:24.633Z
Sorry I thought the unary case is np complete and speed up of unary case leads to eth failure. Am I wrong?
Turbo
CC BY-SA 4.0
2021-03-14T01:01:14.420Z
Also, you might want to look at the $M$-hierarchy.  I think that finding faster parameterized algorithms for the $M$-hierarchy is related to breaking $ETH$ for different versions of formula $SAT$.  However, the parameterized FSA intersection problem is $XNLOGSPACE$-complete (which is pretty hard in the parameterized world) so a result like you suggested could collapse the $M$-hierarchy.
Michael Wehar
CC BY-SA 4.0
2021-03-14T01:09:31.730Z
@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.
Michael Wehar
CC BY-SA 4.0
2021-03-14T01:11:26.527Z
@1.. Note: the unary case is solvable in $O(n^{(1 - \varepsilon) \cdot k})$ time for some $\varepsilon > 0$, but we don't know if it is solvable in $n^{o(k)}$ time.
Michael Wehar
CC BY-SA 4.0
2021-03-14T01:16:19.677Z
Is there a consequence to $XNLOGSPACE$, $k$ $DSA$ intersection, $ETH$ etc if $Parity$-$L=PL=Puniform TC^0$ and $NC^k$ is in $QuasiPuniform$ $TC^0$?
Turbo
CC BY-SA 4.0
2021-03-14T01:21:15.643Z
@1.. Good question!  I don't know the answer.  I have to think about that.  I know that there are a few papers on parameterized logspace complexity classes.  Might be worth doing some reading and searching.  :)
Michael Wehar
CC BY-SA 4.0
2021-03-20T05:42:12.730Z
1. so $k$ dsa intersection in unary case is $W[1]$ complete while binary is in known to be $W[1]$ hard but only known to be in $PSPACE$? 2. Do you know if it is $DSPACE[f(n,k)]$ for perhaps $f(n,k)=n^{O(k)}$ (makes little sense since $k=n$ gives superpolynomial space)? 3. Is $k$ dfa intersection falling under space version of $W$ hierarchy?
Turbo
CC BY-SA 4.0
2021-03-20T06:22:22.053Z
@1.. (1) Binary case is $XNL$-complete.  From one perspective $XNL$ is much harder than the $W$ hierarchy because $k$-weighted formula $SAT$ is in $XL \subseteq XNL$.  However, from another perspective, it is unclear how hard $XNL$ is because we have not yet solved $PTIME$ vs $NL$.  (2) Binary case is in $XNL$ so it is solvable nondeterministically in $k \log(n)$ binary space.  Therefore, it solvable deterministically in $k^2 \cdot \log^2(n)$ binary space by Savitch's Theorem.  (3) What is the space version of the $W$ hierarchy?  Any references would be greatly appreciated.  Thank you!
Michael Wehar
CC BY-SA 4.0
2021-03-20T06:43:16.567Z
Exactly what you stated problems reducible in linear time to klog(n) space and so it appears subset of logspace intersect linear time reducible problems.
Turbo
CC BY-SA 4.0
2021-03-13T23:35:09.963Z
2021-03-14T00:41:54.407Z
2021-03-14T00:41:54.407Z
Michael Wehar
<p>Given <span class="math-container">$k$</span> deterministic FSAs of <span class="math-container">$n$</span> states the intersection of their languages is empty is decidable in <span class="math-container">$n^{o(k)}$</span> time is an open problem.</p>
<ol>
<li><p>For unbounded <span class="math-container">$k$</span> it is known the problem is <span class="math-container">$PSPACE$</span> complete. What is the scale of <span class="math-container">$k$</span> for the problem to be PSPACE complete? Is it <span class="math-container">$k=\Omega(n)$</span>?</p>
</li>
<li><p>What is the consequence the problem is in <span class="math-container">$FPT$</span> having <span class="math-container">$f(k)poly(n)$</span> complexity for <span class="math-container">$f(k)=2^{poly(k)}$</span>?</p>
</li>
<li><p>Is there a result on intersection of deterministic DFSAs which is consistent to <span class="math-container">$CH$</span> is <span class="math-container">$NL$</span> or <span class="math-container">$L$</span> hypothesis (which provides <span class="math-container">$P=CH\neq PSPACE$</span>)?</p>
</li>
</ol>
<p>How about if the <span class="math-container">$FSA$</span>s are all non deterministic?</p>

<cc.complexity-theory><automata-theory><big-picture><regular-language><fixed-parameter-tractable>
DFSA and NFSA intersection problem
Turbo
# DFSA and NFSA intersection problem

(Asked by: username_0 on 2021-03-13)

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?

**Tags:** cc.complexity-theory, automata-theory, big-picture, regular-language, fixed-parameter-tractable

---

## 1 answers

### Answer by username_1 on 2021-03-13. Score: 4 | Accepted answer

**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](http://michaelwehar.com/IntersectionNonEmptiness.html) and [here](http://michaelwehar.com/documents/mwehar_dissertation.pdf).

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

> **Comments:**
> **username_0**: 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$.  
> **username_0**: The answer is not referencing sat. So k dfa intersection in fpt has no implication to eth?  
> **username_1**: @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.  :)  
> **username_1**: @1.. In this paper we looked at the implications regarding ETH, SETH, and circuit lower bounds: https://doi.org/10.1007/978-3-030-48516-0_6  
> **username_1**: @1.. Wow, you ask a lot of questions that I am interested in.  We should chat sometime.  :)  
> **username_0**: 1. What representation do you assume in your answers? 2. So there is no speed up of sat beyond measly falsification of Seth assuming k dfa intersection is in $quasipoly(nk)$?  
> **username_1**: @1.. I generally represent the FSA's (approximately) as directed labeled graphs.  What parameters you are measuring runtime in terms of and how you encode the input can result in some slight differences.  
> **username_1**: @1.. There are some results by Fernau and Krebs regarding breaking ETH.  See here: https://doi.org/10.3390/a10010024  
> **username_0**: Qptime seems to be something I am thinking as an assumption. Let me think.  
> **username_1**: @1.. Also, in my 2014 paper that I mentioned, one of my reductions (see Theorem 7) shows that the problem is still $PSPACE$-complete even for $n$ many FSA's with $O(log(n))$ states each.  In other words, if the FSA intersection problem is in $quasipoly(n \cdot k)$ time, then that should imply that $NSPACE(n) \subseteq QPTIME$.  
> **username_0**: So you represent fsa as -1/0/1 poly(n) sized adjacency matrices?  
> **username_1**: @1.. Adjacency matrices (or adjacency lists) plus information about start and accept states.  
> **username_1**: @1.. How did you start investigating this problem?  I would be interested to hear more about your research direction.  :)  
> **username_0**: Is there a graph theoretic statement of k dsa intersection problem? Like all graphs have an isomorphic path from start to accept state?  
> **username_0**: I am thinking of what would be implications if we allow at most $j$ of the dsa have intersection. Counting, mod_k versions, randomized versions etc of  at most $j$ intersections. These results are not yet in counting frameworks. Path theoretic framework would be helpful. So is there a path theoretic framework?  
> **username_1**: @1.. Actually, there are multiple algebraic problems that are related or equivalent.  You might want to look at the works by Lukas Fleischer and Michael Blondin on this problem.  
> **username_0**: Do they have a path theoretic framework?  
> **username_1**: @1.. I am trying to figure out what that means.  Could you possibly give some example problems to demonstrate what you mean by path theoretic framework?  Also, I think you are onto something regarding question (3).  I still need to think about this a bit.  
> **username_0**: Start state and end states are vertices in graph. A  string is in L iff there is a path from start to end states.  
> **username_1**: @1.. Yes, the classic algorithm is to determine whether there exists a path from a product start state to a product final state in the product automaton's state diagram.  But, this has runtime roughly $O(n^k)$.  
> **username_1**: If you want to continue this discussion outside of stackexchange, please feel welcome to email me.  We could even set up a time to Zoom if you like.  Otherwise, you can continue commenting here.  :)  
> **username_0**: I think it is surprising there is no statement similar to eth fails implies we can speed up k dsa intersection problem. Such a statement would demonstrate eth fails iff k dsa is in faster time and so eth fails implies p not nl.  
> **username_1**: @1.. My initial reaction is that $SAT$ is $NP$-complete and FSA intersection if $PSPACE$-complete so reductions from FSA intersection to $SAT$ are tricky to find because $NP$ vs $PSPACE$ hasn't been solved yet.  
> **username_0**: Sorry I thought the unary case is np complete and speed up of unary case leads to eth failure. Am I wrong?  
> **username_1**: Also, you might want to look at the $M$-hierarchy.  I think that finding faster parameterized algorithms for the $M$-hierarchy is related to breaking $ETH$ for different versions of formula $SAT$.  However, the parameterized FSA intersection problem is $XNLOGSPACE$-complete (which is pretty hard in the parameterized world) so a result like you suggested could collapse the $M$-hierarchy.  
> **username_1**: @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.  
> **username_1**: @1.. Note: the unary case is solvable in $O(n^{(1 - \varepsilon) \cdot k})$ time for some $\varepsilon > 0$, but we don't know if it is solvable in $n^{o(k)}$ time.  
> **username_0**: Is there a consequence to $XNLOGSPACE$, $k$ $DSA$ intersection, $ETH$ etc if $Parity$-$L=PL=Puniform TC^0$ and $NC^k$ is in $QuasiPuniform$ $TC^0$?  
> **username_1**: @1.. Good question!  I don't know the answer.  I have to think about that.  I know that there are a few papers on parameterized logspace complexity classes.  Might be worth doing some reading and searching.  :)  
> **username_0**: 1. so $k$ dsa intersection in unary case is $W[1]$ complete while binary is in known to be $W[1]$ hard but only known to be in $PSPACE$? 2. Do you know if it is $DSPACE[f(n,k)]$ for perhaps $f(n,k)=n^{O(k)}$ (makes little sense since $k=n$ gives superpolynomial space)? 3. Is $k$ dfa intersection falling under space version of $W$ hierarchy?  
> **username_1**: @1.. (1) Binary case is $XNL$-complete.  From one perspective $XNL$ is much harder than the $W$ hierarchy because $k$-weighted formula $SAT$ is in $XL \subseteq XNL$.  However, from another perspective, it is unclear how hard $XNL$ is because we have not yet solved $PTIME$ vs $NL$.  (2) Binary case is in $XNL$ so it is solvable nondeterministically in $k \log(n)$ binary space.  Therefore, it solvable deterministically in $k^2 \cdot \log^2(n)$ binary space by Savitch's Theorem.  (3) What is the space version of the $W$ hierarchy?  Any references would be greatly appreciated.  Thank you!  
> **username_0**: Exactly what you stated problems reducible in linear time to klog(n) space and so it appears subset of logspace intersect linear time reducible problems.  

---

