9

$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$ is NP-hard. [1] [1] E.M. Gold. Complexity of Automaton Identification from Given Data. Information and Control, 37, 302-320 (1978)


7

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’s Minimization Algorithm (longer journal version with more generalizations). They give a (lightly) categorical presentation of Brzowzowski's algorithm, and ...


6

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. Let $g\colon 2^{[m]} \to \mathbb{R}$ be a submodular function. There exists an algorithm that, when given access to an approximate oracle $\mathcal{O}^{\pm}...


6

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 an output with each state). And Theorem 4.3.3 describes how to reverse such a machine.


5

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 Computation, 97, 1-22 (1992)] NL is contained in polyL (deterministic polylogarithmic space). The subset construction can be implemented by a PSPACE transducer, i....


5

The following paper reports on an implementation of the Kameda-Weiner algorithm for computing a minimal NFA, as well on an approach using a SAT solver. I don't know whether the implementation is available, but perhaps you can contact the authors about this. Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing Nondeterministic Finite Automata ...


5

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 automaton as a vector in V=GF(2)n. Let L be a finite language over an alphabet Σ={1, …, k}, and consider an XOR automaton for L with the minimum number of ...


4

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 $F_2$ describing the possible states of the automaton $\mod 2$ after $n$ steps, so $v_n=M^nv_0$, where $v_0=(1,0,..,0)$ describes the starting state. If we know ...


4

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 obtained from the above if we replace "NFA" with "residual finite state automaton". Jiang and Ravikumar showed that the "DFA $\to$ NFA" problem is PSPACE-...


4

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 accepts all strings then its smallest equivalent DFA has size 1, and so a positive answer to your question would imply P=PSPACE.


4

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$ whose truth table is $T$? MIN DNF is known to be NP-complete (see [1] and works cited by it). Since the problem in the post generalizes MIN DNF, the problem ...


2

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, https://doi.org/10.1016/j.tcs.2009.03.022


2

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

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 algorithm constructs a minimum state machine M for a A such that M has as few states as any DFA equivalent to A. This was my original understanding, so the answer ...


1

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 not necessarily minimal.


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