2026-07-21T20:03:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26805 2026-07-09T11:31:08Z ddc:004 open_access

Minimization of Streaming Transducers Bianchini, Christian Puppis, Gabriele Streaming transducers Minimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Bianchini and Gabriele Puppis 2026 Is Part Of LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.LICS.2026.18 urn:nbn:de:0030-drops-268052 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode