Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
10

As you pointed out, there are several ways to define minimal transducers, but I only know of two mathematically appealing definitions. The first result concerns the reduction of linear representations of recognizable series (= defined by weighted automata). The best reference is Chapter II, Minimization, in one of these two books (the more recent is an ...


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

Recall that, in the case of finite state automata, the notion of a minimal automaton is usually meant for deterministic automata only; you can define it for non-deterministic ones, but then you lose two important properties: canonicity (there is a unique minimal deterministic complete automaton for a given regular language, up to state renaming) and the ...


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 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

You can view a FSM transducer from inputs $I$ to outputs $O$ as a normal FSM on alphabet $I\times O$, and use the classic minimization algorithms. For instance if your transducer has transitions labelled by $i|o$, meaning "reading $i$ and outputing $o$", you can just replace the label by $(i,o)$, meaning "reading the pair $(i,o)$". If there are $\epsilon$-...


3

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


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


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