Sequential Tree-to-Word Transducers: Normalization, Minimization, and Learning

Long version of Lata 14 paperWe introduce a class of deterministic sequential top-down tree-to-word transduc- ers (STWs) and investigate a number of its fundamental properties and related problems. First, we investigate the problem of normalization of STWs: we identify a subclass of earliest STWs (eSTWs) that is as expressive as stws and present an effective procedure for converting an arbitrary STW into an equivalent eSTW. We then present a Myhill-Nerode characterization of the class of the transformations definable with STWs which also shows that every transformation defined with an stw has a unique canonical representative eSTW. This canonical eSTW is the minimal eSTW defining the same transformation, and consequently, we present a polynomial minimization procedure for eSTWs, thus giving an effective procedure for constructing the canonical representative of any transformation definable with STWs. Finally, we use the Myhill-Nerode characterization to devise an algorithm for inference (learning) of eSTWs from examples of transformation given by the user. Available at http://chercheurs.lille.inria.fr/~niehren/learning-stw/0.pdf