Minimization of Streaming Transducers
Provides a unified theoretical framework for minimization across multiple transducer models, enabling effective minimization for specific variants.
The paper establishes general criteria for the existence of minimal models of streaming transducers, a broad class that includes several known transducer models. It applies these criteria to obtain effective minimization results for variants of streaming string-to-tree transducers.
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.