Skip to main content

Towards Register Minimisation of Streaming String Transducers

Pierre Alain Reynier ( Aix-Marseille University )

Streaming String Transducers (SST) extend finite-state automata with
registers, used to store partial output words. On each transition, these
registers are updated using concatenation involving registers and 
constant output words. In this work, we focus on deterministic SST 
and consider the problem of register minimisation: given a SST, does
there exist an equivalent SST with at most k registers?
In this talk, I will present how to solve this problem for two subclasses of
SST in which updates do not involve concatenation of registers. Our proof
techniques rely on a generalisation of the twinning property, a property
introduced by Choffrut in 1977. Our results also have consequences for 
(classical) finite-state transducers.

Share this: