We provide general criteria for the existence of minimal models of streaming transducers, namely devices that read an input word and produce an output value by iteratively updating an internal memory. This abstract model subsumes classical (sub)sequential transducers (Schützenberger), streaming string-to-string transducers (Alur-Černý), polynomial automata (Benedikt et al.), and variants of streaming string-to-tree transducers (Alur-D'Antoni). We then instantiate these criteria to obtain effective minimization results for variants of the latter model, where outputs are terms constructed incrementally by extending (tuples of) terms either at the leaves or at the roots.

We tackle the (classic) problem of minimizing (non)deterministic finite automata. The algorithm we put forward has the peculiarity of being incremental, i.e., the minimization proceeds by successive iterations, each producing a partially minimized automaton language-equivalent to the input one. Our algorithm builds upon Almeida et al. from 2014, fixing a minor mistake and generalizing it to the nondeterministic case. It relies on a coloring procedure of a graph associated to the automaton, keeping track of partial information. After dealing with the deterministic case, we extend this idea to the bisimulation-minimization of nondeterministic automata. The algorithms for both the deterministic and the nondeterministic cases run in time O(nm) for an automaton with n states and m transitions. The complexity for the deterministic case matches the complexity claimed by Almeida et al.. The nondeterministic case improves the fastest known incremental algorithm for this problem. We conclude introducing and using a notion of signature of a state, whose aim is to exploit pre-computed information potentially available, to speed-up the process. A signature is used to produce an initial partition of the automaton's states and can be easily integrated in both the incremental and the non-incremental algorithm.