<p>The decision version of the <em>DFA identification</em> problem  (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:</p>

<p><strong>Input:</strong> Integer <span class="math-container">$k$</span> and sets <span class="math-container">$P, N \subseteq \Sigma^*$</span></p>

<p><strong>Question:</strong> Is there a DFA <span class="math-container">$A$</span> with at most <span class="math-container">$k$</span> states such that <span class="math-container">$P \subseteq L(A)$</span> and <span class="math-container">$N \cap L(A) = \emptyset$</span>. In other words <span class="math-container">$A$</span> accepts all words in <span class="math-container">$P$</span> and rejects all words in <span class="math-container">$N$</span>.</p>

<p>See: <a href="https://doi.org/10.1016/S0019-9958(78)90562-4" rel="noreferrer">E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978</a></p>

CC BY-SA 4.0
2020-03-03T22:12:41.193Z
2020-03-03T22:19:49.423Z
2020-03-03T22:19:49.423Z
Marzio De Biasi
<p>Minimizing deterministic Büchi automata is NP-complete, see <a href="https://arxiv.org/abs/1007.1333" rel="noreferrer">Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata</a>.</p>

<p>Deciding whether a coBüchi automaton is determinizable by pruning is also NP-complete, see <a href="https://arxiv.org/abs/1811.00483" rel="noreferrer">Computing the Width of Non-deterministic Automata</a>.</p>

CC BY-SA 4.0
2020-03-03T11:58:52.510Z
2020-03-03T11:58:52.510Z
Denis
<p>Finding the shortest <a href="https://en.wikipedia.org/wiki/Synchronizing_word" rel="noreferrer">synchronizing word</a> for a DFA, if one exists (or more properly testing the existence of a synchronizing word shorter than a parameter <span class="math-container">$k$</span>) is NP-complete.</p>

<p>See my paper: Eppstein, David (1990), "Reset sequences for monotonic automata", <em>SIAM J. Comput.</em> 19 (3): 500–510, <a href="https://doi.org/10.1137/0219033" rel="noreferrer">doi:10.1137/0219033</a>, Theorem 8.</p>

CC BY-SA 4.0
2020-03-20T04:21:13.337Z
2020-03-20T04:21:13.337Z
David Eppstein
<p>Here is another NP-complete variation of the DFA intersection non-emptiness problem.</p>

<p>(1) Given a list of DFA's and a number <span class="math-container">$n$</span> (in unary), does there exist a string of length at most <span class="math-container">$n$</span> that is accepted by all of the DFA's?</p>

<p>Also, here are two NP-complete variations of the DFA non-emptiness problem.</p>

<p>(2) Given a 2DFA and a number <span class="math-container">$n$</span> (in unary), does there exist a string of length at most <span class="math-container">$n$</span> that is accepted by the 2DFA?</p>

<p>(3) Consider an infinite set of variables <span class="math-container">$\Sigma := \{ x_i \}_{i \in \mathbb{N}}$</span>.  A mask is a finite sequence of variables from <span class="math-container">$\Sigma$</span>.  Given a mask <span class="math-container">$m$</span> and a DFA <span class="math-container">$D$</span>, does there exist a binary assignment to the variables from <span class="math-container">$m$</span> such that <span class="math-container">$D$</span> accepts <span class="math-container">$m$</span>?</p>

<hr>

<p><strong>Update</strong></p>

<p>The three problems above are all <span class="math-container">$NP$</span>-complete.  They are in <span class="math-container">$NP$</span> because they have polynomial time verifiers with polynomial size certificates.</p>

<p>Below I will add some justification for <span class="math-container">$NP$</span>-hardness.</p>

<p><strong>3-SAT is reducible to (1):</strong> Follows by essentially the same argument as in Theorem 1 from "Detecting patterns in finite regular and context-free languages".  It's also worth looking at "The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata" where a related problem denoted by <span class="math-container">$BDFAI_R$</span> is investigated.</p>

<p><strong>(1) is reducible to (2):</strong> By 2DFA, we mean a two-way deterministic finite automata.  The following observation is sufficient.  Given a set of <span class="math-container">$k$</span> DFA's <span class="math-container">$\{ D_i \}_{i \in [k]}$</span> with <span class="math-container">$n$</span> states each, we can construct a 2DFA <span class="math-container">$X$</span> with roughly <span class="math-container">$k \cdot n$</span> states such that <span class="math-container">$L(X) = \cap_{i \in [k]} L(D_i)$</span>.  Essentially, <span class="math-container">$X$</span> reads over the input string <span class="math-container">$k$</span> times simulating each of the <span class="math-container">$k$</span> DFA's one at a time.</p>

<p><strong>3-SAT is reducible to (3):</strong></p>

<p>Let a 3-CNF Boolean formula <span class="math-container">$\phi$</span> with <span class="math-container">$m$</span> 3-CNF clauses, <span class="math-container">$n$</span> variables, and <span class="math-container">$l$</span> literal occurrences be given.  We construct a DFA with <span class="math-container">$O(m+n+l)$</span> states that reads in a sequence of <span class="math-container">$2 \cdot l$</span> bits.  The DFA reads in one pair of bits for each literal occurrence.  For each pair of bits, the first bit represents the sign of the associated literal (positive or negated) and the second bit represents the value assigned to its variable.  The DFA accepts if all of the signs match the formula <span class="math-container">$\phi$</span> and if each block of three pairs of bits corresponds with a satisfied 3-CNF clause.  Also, we construct a mask of length <span class="math-container">$2 \cdot l$</span> that makes sure that the assignment is consistent for each variable.  Consistent means that all occurrences of the same variable are assigned the same value.  The mask has <span class="math-container">$l + n$</span> variables where <span class="math-container">$l$</span> are used for the signs of literals and <span class="math-container">$n$</span> are used for the variables of <span class="math-container">$\phi$</span>.  In other words, <span class="math-container">$l$</span> are used for the first bits of the pairs and <span class="math-container">$n$</span> are used for the second bits of the pairs.</p>

CC BY-SA 4.0
2020-03-06T10:40:08.350Z
For your problem (1), I guess $n$ must be given in unary coding, or does it also hold if given in binary coding?
StefanH
CC BY-SA 4.0
2020-03-06T19:44:11.930Z
@StefanH Yes, the number $n$ is represented in unary for (1) and (2).  Thank you very much for making this important point!
Michael Wehar
CC BY-SA 4.0
2020-03-08T00:24:31.767Z
@StefanH If $n$ is written in binary, then I think that (1) and (2) would be PSPACE-complete.
Michael Wehar
CC BY-SA 4.0
2020-03-08T00:25:17.157Z
If anyone is interested in seeing any of the proofs, please let me know.  Thank you!  :)
Michael Wehar
CC BY-SA 4.0
2020-03-08T18:07:54.400Z
Would be nice if you add the proofs.
StefanH
CC BY-SA 4.0
2020-03-18T03:34:48.427Z
@StefanH Thank you for the follow-up!  I just added proof sketches.  :)
Michael Wehar
CC BY-SA 4.0
2020-03-06T07:09:01.663Z
2020-03-18T03:31:36.093Z
2020-03-18T03:31:36.093Z
Michael Wehar
<p>The following (discussed in <a href="https://cs.stackexchange.com/q/140412/82288">another thread</a>, and as of this edit I don't know the answer yet) is Problem 7.36 from Sipser Third edition:</p>
<blockquote>
<p>Show that the following problem is NP-complete. You are given a set of states <span class="math-container">$Q = \{ q_0, q_1, \ldots, q_l\}$</span> and a collection of pairs <span class="math-container">$\{ (s_1, r_1), \ldots, (s_k, r_k)\}$</span> where the <span class="math-container">$s_i$</span> are distinct bitstrings and <span class="math-container">$r_i$</span> are (not necessarily distinct) members of <span class="math-container">$Q$</span>. Determine whether a DFA exists for which starting at the start state and reading each <span class="math-container">$s_i$</span> leads to state <span class="math-container">$r_i$</span>.</p>
</blockquote>

CC BY-SA 4.0
2021-05-16T03:35:58.050Z
2021-05-17T00:10:01.190Z
2021-05-17T00:10:01.190Z
xdavidliu
<p>A nice question! Time to get Garey and Johnson off the shelf once again. Problem [AL2] in the problem list mentions the following: The nonemptiness problem for deterministic 2-way deterministic finite automata (2DFAs) over unary alphabet is NP-complete. </p>

<p>Zvi Galil: Hierarchies of complete problems. Acta Informat. 6, 77-88.</p>

<p>Another problem that comes to mind concerns a slight extension of determinism for 1-way finite automata: For deterministic finite automata with multiple initial states (MDFAs), the minimization problem is NP-complete. Although I do not really consider this to be a "deterministic" automaton model, it is a curious result and I feel that the area is close enough to mention it.</p>

<p>Andreas Malcher: <a href="https://doi.org/10.1016/j.tcs.2004.03.070" rel="nofollow noreferrer">Minimizing finite automata is computationally hard.</a> Theor. Comput. Sci. 327(3): 375-390 (2004)</p>

CC BY-SA 4.0
2020-03-19T22:10:40.057Z
2020-03-24T21:25:26.830Z
2020-03-24T21:25:26.830Z
Hermann Gruber
<p>Consider the following problem:</p>
<p>Given two DFAs <span class="math-container">$A_1, A_2$</span> and an integer <span class="math-container">$k\in\mathbb{N}$</span>. Decide whether there is a <span class="math-container">$k$</span>-state DFA <span class="math-container">$A_{sep}$</span> such that  <span class="math-container">$\mathcal{L}(A_{sep}) \subseteq \mathcal{L}(A_1)$</span> if and only if <span class="math-container">$\mathcal{L}(A_{sep}) \not\subseteq \mathcal{L}(A_2)$</span>.</p>
<p>This problem is NP-complete. I've posted a short note describing the proof: <a href="https://arxiv.org/pdf/2306.03533.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/2306.03533.pdf</a>.</p>
<p>A corollary of this construction is that deciding for an automaton, and a <span class="math-container">$k\in\mathbb{N}$</span>, there is a word <span class="math-container">$w\in \Sigma^k$</span> such that for every <span class="math-container">$n\in\mathbb{N}$</span> the automaton accepts <span class="math-container">$w^n$</span> is NP-complete.</p>

CC BY-SA 4.0
2023-07-06T12:33:51.993Z
2023-07-06T19:43:14.740Z
2023-07-06T19:43:14.740Z
Janmar
<p>A result relating to DFAs(or Failure DFAs) and compressibility that shows NP-completeness via failure transitions - <a href="http://umu.diva-portal.org/smash/record.jsf?pid=diva2%3A747628&dswid=-3560" rel="nofollow noreferrer"> this work </a> relates to whether there are efficient algorithms for DFA compressibility</p>
<p>Another result based on Gold's (reference in the other answer) Grammatical Inference framework that shows Minimal Separating Automata is NP-complete, Related to Minimum Seperating Set, in the context of Muller Automata - <a href="https://www.sciencedirect.com/science/article/pii/S030439759900016X" rel="nofollow noreferrer"> Seperating sets' acceptance criteria</a> and their NP-completeness.</p>
<p><strong>Update</strong></p>
<p>More recent work on the decidability of distinguishing DFAs and NP completeness. See the reference in the link below<a href="https://research.tue.nl/en/publications/deciding-minimal-distinguishing-dfas-is-np-complete" rel="nofollow noreferrer"> Deciding Minimal Distinguishing DFAs is NP-complete </a>.</p>

CC BY-SA 4.0
2021-05-18T21:09:58.670Z
The first result is really nice, I didn't know about this! Regarding the second paper in your answer: from the abstract I understand that the paper gives a condition under which Gold's NP-complete problem is in P, rather than showing that something is NP-complete. I didn't read the paper though because it is paywalled. Here is the official link to the paper via doi (digital object identifier): https://doi.org/10.1016/j.ins.2016.07.053
Hermann Gruber
CC BY-SA 4.0
2021-05-18T22:30:41.727Z
@HermannGruber correct!  was completing answer, had to check reference for the Muller Automata, thanks.
user3483902
CC BY-SA 4.0
2021-05-18T11:42:46.180Z
2024-01-06T19:07:14.347Z
2024-01-06T19:07:14.347Z
user3483902
<p>Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (<a href="https://en.wikipedia.org/wiki/List_of_NP-complete_problems" rel="noreferrer">see</a>, or <a href="https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems" rel="noreferrer">here</a>) graph theoretical, or involve some string rewriting or things like that.</p>

<p>The only problem that comes to my mind is the DFA-INTERSECTION-NONEMPTINESS for unary automata. Given <span class="math-container">$k$</span> deterministic automata, this problem is to decide if they accept some common word. In this generality the problem is PSPACE-complete, but for unary automata it is NP-complete.</p>

<p>But beside from that, no other decision problem from the realm of finite automata theory come to my mind. So do you know any?</p>

CC BY-SA 4.0
2020-03-03T08:35:19.923Z
I'd expect computing the pumping length to be NP-complete. And apparently containing a word with some fixed factor is also NP-complete: "Detecting patterns in finite regular and context-free
languages"
xavierm02
CC BY-SA 4.0
2020-03-03T11:21:21.820Z
@xavierm02 Nice paper. Regarding pumping length, do you mean the pumping constant. That is simple the number of states, and if you ask for a minimal pumping constant, then this is the largest accepting path without cycles, which seems to be equivalent to this problem, https://en.wikipedia.org/wiki/Longest_path_problem Hence NP-complete.
StefanH
CC BY-SA 4.0
2020-03-03T15:20:14.243Z
I meant minimal pumping constant. And yes, the longest simple path problem seems to easily reduce to it.
xavierm02
CC BY-SA 4.0
2020-03-04T21:28:29.257Z
This is another variant (clearly linked to the *pumping length problem* suggested by @xavierm02): Hamiltonian cycle problem on max-degree-3 directed graphs is NP-complete so checking if a DFA accepts a string of length $k$ that contains no repeated character is also NP-complete  (use the same graph and label each edge with a different character, pick a node as the only starting and accepting state, add missing transitions to a dummy non accepting state)
Marzio De Biasi
CC BY-SA 4.0
2020-03-19T07:27:37.167Z
@StefanH I disagree. The pumping length problem does not involve the deterministic state complexity (number of states in minimum DFA) but nondeterministic state complexity, which is more difficult to determine. The associated decision problem of the latter is PSPACE-complete, so the NP-completeness argument is flawed. There is a classic metatheorem (in the style of Greibach's undecidability metatheorem) that roughly states that most interesting problems for a given NFA are PSPACE-complete. I am confident that the theorem applies here as well
Hermann Gruber
<cc.complexity-theory><np-hardness><fl.formal-languages><automata-theory><np-complete>
NP-complete decision problems on deterministic automata
StefanH
# NP-complete decision problems on deterministic automata

(Asked by: username_0 on 2020-03-02)

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either ([see](https://en.wikipedia.org/wiki/List_of_NP-complete_problems), or [here](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems)) graph theoretical, or involve some string rewriting or things like that.

The only problem that comes to my mind is the DFA-INTERSECTION-NONEMPTINESS for unary automata. Given $k$ deterministic automata, this problem is to decide if they accept some common word. In this generality the problem is PSPACE-complete, but for unary automata it is NP-complete.

But beside from that, no other decision problem from the realm of finite automata theory come to my mind. So do you know any?

**Tags:** cc.complexity-theory, np-hardness, fl.formal-languages, automata-theory, np-complete
> **Comments:**
> **username_1**: I'd expect computing the pumping length to be NP-complete. And apparently containing a word with some fixed factor is also NP-complete: "Detecting patterns in finite regular and context-free
 languages"  
> **username_0**: @xavierm02 Nice paper. Regarding pumping length, do you mean the pumping constant. That is simple the number of states, and if you ask for a minimal pumping constant, then this is the largest accepting path without cycles, which seems to be equivalent to this problem, https://en.wikipedia.org/wiki/Longest_path_problem Hence NP-complete.  
> **username_1**: I meant minimal pumping constant. And yes, the longest simple path problem seems to easily reduce to it.  
> **username_2**: This is another variant (clearly linked to the *pumping length problem* suggested by @xavierm02): Hamiltonian cycle problem on max-degree-3 directed graphs is NP-complete so checking if a DFA accepts a string of length $k$ that contains no repeated character is also NP-complete  (use the same graph and label each edge with a different character, pick a node as the only starting and accepting state, add missing transitions to a dummy non accepting state)  
> **username_3**: @StefanH I disagree. The pumping length problem does not involve the deterministic state complexity (number of states in minimum DFA) but nondeterministic state complexity, which is more difficult to determine. The associated decision problem of the latter is PSPACE-complete, so the NP-completeness argument is flawed. There is a classic metatheorem (in the style of Greibach's undecidability metatheorem) that roughly states that most interesting problems for a given NFA are PSPACE-complete. I am confident that the theorem applies here as well  

---

## 8 answers

### Answer by username_2 on 2020-03-03. Score: 12

The decision version of the *DFA identification* problem (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:

**Input:** Integer $k$ and sets $P, N \subseteq \Sigma^\*$

**Question:** Is there a DFA $A$ with at most $k$ states such that $P \subseteq L(A)$ and $N \cap L(A) = \emptyset$. In other words $A$ accepts all words in $P$ and rejects all words in $N$.

See: [E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978](https://doi.org/10.1016/S0019-9958(78)90562-4)


---

### Answer by username_4 on 2020-03-03. Score: 8

Minimizing deterministic Büchi automata is NP-complete, see [Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata](https://arxiv.org/abs/1007.1333).

Deciding whether a coBüchi automaton is determinizable by pruning is also NP-complete, see [Computing the Width of Non-deterministic Automata](https://arxiv.org/abs/1811.00483).


---

### Answer by username_5 on 2020-03-20. Score: 5

Finding the shortest [synchronizing word](https://en.wikipedia.org/wiki/Synchronizing_word) for a DFA, if one exists (or more properly testing the existence of a synchronizing word shorter than a parameter $k$) is NP-complete.

See my paper: Eppstein, David (1990), "Reset sequences for monotonic automata", *SIAM J. Comput.* 19 (3): 500–510, [doi:10.1137/0219033](https://doi.org/10.1137/0219033), Theorem 8.


---

### Answer by username_6 on 2020-03-06. Score: 4

Here is another NP-complete variation of the DFA intersection non-emptiness problem.

(1) Given a list of DFA's and a number $n$ (in unary), does there exist a string of length at most $n$ that is accepted by all of the DFA's?

Also, here are two NP-complete variations of the DFA non-emptiness problem.

(2) Given a 2DFA and a number $n$ (in unary), does there exist a string of length at most $n$ that is accepted by the 2DFA?

(3) Consider an infinite set of variables $\Sigma := \{ x\_i \}\_{i \in \mathbb{N}}$. A mask is a finite sequence of variables from $\Sigma$. Given a mask $m$ and a DFA $D$, does there exist a binary assignment to the variables from $m$ such that $D$ accepts $m$?

---

**Update**

The three problems above are all $NP$-complete. They are in $NP$ because they have polynomial time verifiers with polynomial size certificates.

Below I will add some justification for $NP$-hardness.

**3-SAT is reducible to (1):** Follows by essentially the same argument as in Theorem 1 from "Detecting patterns in finite regular and context-free languages". It's also worth looking at "The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata" where a related problem denoted by $BDFAI\_R$ is investigated.

**(1) is reducible to (2):** By 2DFA, we mean a two-way deterministic finite automata. The following observation is sufficient. Given a set of $k$ DFA's $\{ D\_i \}\_{i \in [k]}$ with $n$ states each, we can construct a 2DFA $X$ with roughly $k \cdot n$ states such that $L(X) = \cap\_{i \in [k]} L(D\_i)$. Essentially, $X$ reads over the input string $k$ times simulating each of the $k$ DFA's one at a time.

**3-SAT is reducible to (3):**

Let a 3-CNF Boolean formula $\phi$ with $m$ 3-CNF clauses, $n$ variables, and $l$ literal occurrences be given. We construct a DFA with $O(m+n+l)$ states that reads in a sequence of $2 \cdot l$ bits. The DFA reads in one pair of bits for each literal occurrence. For each pair of bits, the first bit represents the sign of the associated literal (positive or negated) and the second bit represents the value assigned to its variable. The DFA accepts if all of the signs match the formula $\phi$ and if each block of three pairs of bits corresponds with a satisfied 3-CNF clause. Also, we construct a mask of length $2 \cdot l$ that makes sure that the assignment is consistent for each variable. Consistent means that all occurrences of the same variable are assigned the same value. The mask has $l + n$ variables where $l$ are used for the signs of literals and $n$ are used for the variables of $\phi$. In other words, $l$ are used for the first bits of the pairs and $n$ are used for the second bits of the pairs.

> **Comments:**
> **username_0**: For your problem (1), I guess $n$ must be given in unary coding, or does it also hold if given in binary coding?  
> **username_6**: @StefanH Yes, the number $n$ is represented in unary for (1) and (2).  Thank you very much for making this important point!  
> **username_6**: @StefanH If $n$ is written in binary, then I think that (1) and (2) would be PSPACE-complete.  
> **username_6**: If anyone is interested in seeing any of the proofs, please let me know.  Thank you!  :)  
> **username_0**: Would be nice if you add the proofs.  
> **username_6**: @StefanH Thank you for the follow-up!  I just added proof sketches.  :)  

---

### Answer by username_7 on 2021-05-16. Score: 4

The following (discussed in [another thread](https://cs.stackexchange.com/q/140412/82288), and as of this edit I don't know the answer yet) is Problem 7.36 from Sipser Third edition:

> Show that the following problem is NP-complete. You are given a set of states $Q = \{ q\_0, q\_1, \ldots, q\_l\}$ and a collection of pairs $\{ (s\_1, r\_1), \ldots, (s\_k, r\_k)\}$ where the $s\_i$ are distinct bitstrings and $r\_i$ are (not necessarily distinct) members of $Q$. Determine whether a DFA exists for which starting at the start state and reading each $s\_i$ leads to state $r\_i$.


---

### Answer by username_3 on 2020-03-19. Score: 4

A nice question! Time to get Garey and Johnson off the shelf once again. Problem [AL2] in the problem list mentions the following: The nonemptiness problem for deterministic 2-way deterministic finite automata (2DFAs) over unary alphabet is NP-complete.

Zvi Galil: Hierarchies of complete problems. Acta Informat. 6, 77-88.

Another problem that comes to mind concerns a slight extension of determinism for 1-way finite automata: For deterministic finite automata with multiple initial states (MDFAs), the minimization problem is NP-complete. Although I do not really consider this to be a "deterministic" automaton model, it is a curious result and I feel that the area is close enough to mention it.

Andreas Malcher: [Minimizing finite automata is computationally hard.](https://doi.org/10.1016/j.tcs.2004.03.070) Theor. Comput. Sci. 327(3): 375-390 (2004)


---

### Answer by username_8 on 2023-07-06. Score: 3

Consider the following problem:

Given two DFAs $A\_1, A\_2$ and an integer $k\in\mathbb{N}$. Decide whether there is a $k$-state DFA $A\_{sep}$ such that $\mathcal{L}(A\_{sep}) \subseteq \mathcal{L}(A\_1)$ if and only if $\mathcal{L}(A\_{sep}) \not\subseteq \mathcal{L}(A\_2)$.

This problem is NP-complete. I've posted a short note describing the proof: <https://arxiv.org/pdf/2306.03533.pdf>.

A corollary of this construction is that deciding for an automaton, and a $k\in\mathbb{N}$, there is a word $w\in \Sigma^k$ such that for every $n\in\mathbb{N}$ the automaton accepts $w^n$ is NP-complete.


---

### Answer by username_9 on 2021-05-18. Score: 3

A result relating to DFAs(or Failure DFAs) and compressibility that shows NP-completeness via failure transitions -  [this work](http://umu.diva-portal.org/smash/record.jsf?pid=diva2%3A747628&dswid=-3560)  relates to whether there are efficient algorithms for DFA compressibility

Another result based on Gold's (reference in the other answer) Grammatical Inference framework that shows Minimal Separating Automata is NP-complete, Related to Minimum Seperating Set, in the context of Muller Automata -  [Seperating sets' acceptance criteria](https://www.sciencedirect.com/science/article/pii/S030439759900016X) and their NP-completeness.

**Update**

More recent work on the decidability of distinguishing DFAs and NP completeness. See the reference in the link below [Deciding Minimal Distinguishing DFAs is NP-complete](https://research.tue.nl/en/publications/deciding-minimal-distinguishing-dfas-is-np-complete) .

> **Comments:**
> **username_3**: The first result is really nice, I didn't know about this! Regarding the second paper in your answer: from the abstract I understand that the paper gives a condition under which Gold's NP-complete problem is in P, rather than showing that something is NP-complete. I didn't read the paper though because it is paywalled. Here is the official link to the paper via doi (digital object identifier): https://doi.org/10.1016/j.ins.2016.07.053  
> **username_9**: @HermannGruber correct!  was completing answer, had to check reference for the Muller Automata, thanks.  

---

