Paper: Minimization of Streaming Transducers (at LICS 2026)

Authors: Christian Bianchini Gabriele Puppis

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.18

Abstract

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.

BibTeX

  @InProceedings{BianchiniPuppis-MinimizationofStrea,
    author = 	 {Christian Bianchini and Gabriele Puppis},
    title = 	 {Minimization of Streaming Transducers},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {18:1--18:28},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.18}
  }