# NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) 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?

• 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" Mar 3 '20 at 8:35
• @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, en.wikipedia.org/wiki/Longest_path_problem Hence NP-complete. Mar 3 '20 at 11:21
• I meant minimal pumping constant. And yes, the longest simple path problem seems to easily reduce to it. Mar 3 '20 at 15:20
• 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) Mar 4 '20 at 21:28
• @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 Mar 19 '20 at 7:27

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

Minimizing deterministic Büchi automata is NP-complete, see Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata.

Deciding whether a coBüchi automaton is determinizable by pruning is also NP-complete, see Computing the Width of Non-deterministic Automata.

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.

• For your problem (1), I guess $n$ must be given in unary coding, or does it also hold if given in binary coding? Mar 6 '20 at 10:40
• @StefanH Yes, the number $n$ is represented in unary for (1) and (2). Thank you very much for making this important point! Mar 6 '20 at 19:44
• If anyone is interested in seeing any of the proofs, please let me know. Thank you! :) Mar 8 '20 at 0:25
• Would be nice if you add the proofs. Mar 8 '20 at 18:07
• @StefanH Thank you for the follow-up! I just added proof sketches. :) Mar 18 '20 at 3:34

Finding the shortest 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, Theorem 8.

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. Theor. Comput. Sci. 327(3): 375-390 (2004)

The following (discussed in another thread, 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$$.

A result relating to DFAs(or Failure DFAs) and compressibility that shows NP-completeness via failure transitions - this work 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 and their NP-completeness.

• 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): doi.org/10.1016/j.ins.2016.07.053 May 18 at 21:09
• @HermannGruber correct! was completing answer, had to check reference for the Muller Automata, thanks. May 18 at 22:30