LogoGDRIM_100px.png

Journées Nationales 2018
du GDR Informatique Mathématique

Du 3 au 6 avril 2018
École polytechnique, Palaiseau, France

Register Minimisation of Streaming String Transducers
Pierre-Alain Reynier  1  
1 : Aix-Marseille Université, LIS
-

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.


Personnes connectées : 1