# 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’...
• 31.7k
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,341

### 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 ...
• 6,898
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 ...
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.1k
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 ...
• 16.3k