# 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

### Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

The answer to your question is yes. See Bonchi, Bonsangue, Rutten and Silva's papers Brzozowski's algorithm (co)algebraically (shorter conference version) and Algebra-Coalgebra Duality in Brzozowski’...
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....

### Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

Just to add to Neel's answer, in my book Automatic Sequences with Jean-Paul Allouche we discuss DFAO's (deterministic finite automata with outputs), which are exactly what you asked about (associate ...
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 ...
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 ...
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$ ...

### 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, ...
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.
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 ...
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 ...

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