Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
9 votes
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$ ...
Dmitri Urbanowicz's user avatar
6 votes
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 ...
Aryeh's user avatar
  • 10.6k
6 votes
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....
Clement C.'s user avatar
  • 4,471
5 votes
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 ...
Stefan Kiefer's user avatar
4 votes

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 ...
Hermann Gruber's user avatar
4 votes
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$ ...
Neal Young's user avatar
  • 10.8k
2 votes

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, ...
Hermann Gruber's user avatar
2 votes
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.
Shaull's user avatar
  • 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 ...
Makketronix's user avatar
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 ...
Mikolas's user avatar
  • 1,322

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