Minimization of Streaming Transducers

2026/05/11 by Christian Bianchini, Gabriele Puppis · 1 voice
Computer Science · #cs.FL #cs.LO

paper · pdf · doi:10.48550/arxiv.2605.11190

arxiv published 2026/05/11 · arxiv updated 2026/05/13

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.

Citations

• Minimizing Streaming String Transducers: An algebraic approach
• Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
• Minimizing Cost Register Automata over a Field
• Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
• First-order separation over countable ordinals
• Learning automata and transducers: a categorical approach
• Noncommutative rational Pólya series
• Equivalence of finite-valued streaming string transducers is decidable
• Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method"
• Learning Nominal Automata
• Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
• First-order definable string transformations
• Logics with rigidly guarded data tests
• Automata theory in nominal sets
• Transducers with origin information
• Decision Problems for Additive Regular Functions
• Streaming Tree Transducers
• A note on Ritt's theorem on decomposition of polynomials
• Learning regular sets from queries and counterexamples
• An Efficient Unification Algorithm
• On finite monoids having only trivial subgroups
• A Machine-Oriented Logic Based on the Resolution Principle
• Prime and composite polynomials
• Ueber die Theorie der algebraischen Formen

Discussions

• Christian Bianchini, Gabriele Puppis: Minimization of Streaming Transducers https://arxiv.org/abs/2605.11190 https://arxiv.org/pdf/2605.11190 https://arxiv.org/html/2605.11190 [bsky, 0 points, 0 comments]

Related

• Minimizing Streaming String Transducers: An algebraic approach
• Register transducers are marble transducers
• Transducers with origin information
• Streaming Transformations of Infinite Ordered-Data Words
• What You Must Remember When Transforming Datawords