DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.18

Minimization of Streaming Transducers

Authors: Christian Bianchini and Gabriele Puppis

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

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.

Cite as

Christian Bianchini and Gabriele Puppis. Minimization of Streaming Transducers. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 18:1-18:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bianchini_et_al:LIPIcs.LICS.2026.18,
  author =	{Bianchini, Christian and Puppis, Gabriele},
  title =	{{Minimization of Streaming Transducers}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{18:1--18:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.18},
  URN =		{urn:nbn:de:0030-drops-268052},
  doi =		{10.4230/LIPIcs.LICS.2026.18},
  annote =	{Keywords: Streaming transducers, Minimization}
}

Search Results

Documents authored by Bianchini, Christian

Minimization of Streaming Transducers

Abstract

Cite as

Thanks for your feedback!

Could not send message