8
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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" $\endgroup$
    – xavierm02
    Mar 3, 2020 at 8:35
  • $\begingroup$ @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. $\endgroup$
    – StefanH
    Mar 3, 2020 at 11:21
  • $\begingroup$ I meant minimal pumping constant. And yes, the longest simple path problem seems to easily reduce to it. $\endgroup$
    – xavierm02
    Mar 3, 2020 at 15:20
  • 1
    $\begingroup$ 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) $\endgroup$
    – Marzio De Biasi
    Mar 4, 2020 at 21:28
  • $\begingroup$ @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 $\endgroup$
    – Hermann Gruber
    Mar 19, 2020 at 7:27

7 Answers 7

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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)

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Hermann Gruber
    May 18, 2021 at 21:09
  • 1
    $\begingroup$ @HermannGruber correct! was completing answer, had to check reference for the Muller Automata, thanks. $\endgroup$
    – user3483902
    May 18, 2021 at 22:30

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.