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$ ...
user avatar
7 votes
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’...
user avatar
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....
user avatar
  • 4,341
6 votes

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 ...
user avatar
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 ...
user avatar
5 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 ...
user avatar
  • 10.1k
5 votes
Accepted

Does XOR automata (NXA) for finite languages benefit from cycles?

I think that the answer is the affirmative. Maybe there is a simpler proof, but here is a sketch of a proof which uses linear algebra. Like domotorp, we will view a configuration of an n-state XOR ...
user avatar
  • 16.3k
4 votes

Does XOR automata (NXA) for finite languages benefit from cycles?

I think I can prove that cycles do not help over the unary alphabet. Consider the matrix $M$ over $F_2$ describing from which state into which state we can get in one step and the vector $v_n$ over $...
user avatar
  • 13.5k
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 ...
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$ ...
user avatar
  • 8,273
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, ...
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.
user avatar
  • 5,261
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 ...
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 ...
user avatar
  • 1,312

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