Towards Register Minimisation of Streaming String Transducers
Pierre Alain Reynier ( Aix-Marseille University )
- 11:00 22nd February 2018 ( week 6, Hilary Term 2018 )Tony Hoare Room - Robert Hooke Building
Abstract:
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:
