Learning Sequential Tree-to-Word Transducers

International audienceWe study the problem of learning sequential top-down tree-to- word transducers (STWs). First, we present a Myhill-Nerode characterization of the corresponding class of sequential tree-to-word transformations (STW). Next, we investigate what learning of stws means, identify fundamental obstacles, and propose a learning model with abstain. Finally, we present a polynomial learning algorithm.A long version is available here