7
$\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?

$\endgroup$
  • 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 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 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 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 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 at 7:27
10
$\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

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

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

$\endgroup$
  • 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 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 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 at 0:25
  • 1
    $\begingroup$ Would be nice if you add the proofs. $\endgroup$ – StefanH Mar 8 at 18:07
  • 1
    $\begingroup$ @StefanH Thank you for the follow-up! I just added proof sketches. :) $\endgroup$ – Michael Wehar Mar 18 at 3:34
3
$\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)

$\endgroup$
2
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.