# Tag Info

Accepted

### Finding a minimal DFA whose language has a desired intersection with another

$M_C$ must accept every word of $S^+ = B$ and reject every word of $S^- = A \setminus B$. Let $A$ and $B$ be finite and such that both $S^+$ and $S^-$ are non-empty. Then exact computation of $M_C$ ...
Accepted

### Can we efficiently convert from NFA to smallest equivalent DFA?

See here: https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings "checking whether an NFA accepts all strings is PSPACE-complete". In particular, if an NFA ...
• 10.6k
Accepted

### Minimizing a submodular function given noisy oracle access

A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]). Corollary 5....
• 4,471
Accepted

### Complexity of NFA to DFA minimization with binary threshold

The problem is in PSPACE, hence is PSPACE-complete. DFA minimization is in NL; see Theorem 2.1 of [S. Cho and D.T. Huynh. The Parallel Complexity of Finite-State Automata Problems. Information and ...

### Minimizing residual finite state automata

Let the "DFA $\to$ NFA" problem denote the following: Given a DFA $A$ and an integer $k$, is there an NFA with at most $k$ states equivalent to $A$? Similarly, let "DFA $\to$ RFSA" denote the problem ...
• 6,515
Accepted

### Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?

Theorem 1. The problem in the post is NP-complete. Proof. MIN DNF is the following special case of the problem in the post: Given a truth table $T$ and integer $k$, is there a DNF of size at most $k$ ...
• 10.8k

### Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?

Yes, see for example here: Johanna HĂ¶gberg, Andreas Maletti, Jonathan May, Backward and forward bisimulation minimization of tree automata, Theoretical Computer Science 410(37), 2009, pp. 3539-3552, ...
• 6,515
Accepted

### Epsilon-closure and DFA minimization algorithms for probabilistic NFA

Stefan Kiefer has some work on minimization of probabilistic automata. This should probably put you on the right track: https://arxiv.org/abs/1404.6673.
• 5,646
1 vote
Accepted

### NP-Completeness of Finding Minimum Automaton, in Gold's paper

After more and more digging, here is what I found: First reference: Introduction to Automata Theory, Languages, and Computation 3rd Edition. Specifically, theorem 4.26 indicates that the provided ...
• 146
1 vote

### How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it

For 3 inputs it's not $2^3$ functions but $2^{2^3}$ functions. Circuit minimization is generally hard. You could try using the aiger package http://fmv.jku.at/aiger/, which will give you a circuit but ...
• 1,322

Only top scored, non community-wiki answers of a minimum length are eligible