Minimizing Streaming String Transducers: An algebraic approach
For researchers in automata theory and formal verification, this provides complexity results and algorithms for minimizing rational functions represented as aSST.
The paper addresses minimization of streaming string transducers (aSST) by leveraging an algebraic approach via bimachines. It establishes a bijection between a subclass of aSST and bimachines, yielding Ptime (register) and NP (both states and registers) minimization procedures, and proves register minimization with a fixed automaton is NP-complete.
In this work, we study minimization of rational functions given as appending streaming string transducers (aSST for short). We rely on an algebraic presentation of these functions, known as bimachines, to address the minimization of both states and registers of aSST. First, we show a bijection between a subclass of aSST and bimachines, which maps the numbers of states and registers of the aSST to two natural parameters of the bimachine. Using known results on the minimization of bimachines, this yields a Ptime (resp. NP) procedure to minimize this subclass of aSST with respect to registers (resp. both states and registers). In a second step, we introduce a new model of bimachines, named asynchronous bimachines, which allows to lift the bijection to the whole class of aSST. Based on this, we prove that register minimization with a fixed underlying automaton is NP-complete.