Adrien Boiret will give a presentation on Tuesday, 19th March at 2pm in room A008.
His talk is entitled “Extend the RPNI algorithm for Symbolic Learning to Transducers with Lookahead”.
We consider the problem of passive symbolic learning of tree and word transducers.
Symbolic learning means learning an exact target (automaton, transducer…) using exact information on its (words, input/output pairs…).
The passive learning problem deals with identifying a specific transducer in normal form from a finite set of behaviour examples (as opposed to the active learning that uses student-teacher interactions).
Symbolic learning problems are solved in word languages using the RPNI algorithm, that relies heavily on the Myhill-Nerode characterization of a minimal normal form on DFA.
The extensions of RPNI to word transformations and tree languages follow the same pattern: first, a Myhill-Nerode theorem is identified, then the normal form it induces can be learnt from examples.
In this talk I will present another extension of the RPNI model that necessitates a departure from this schema to learn rational functions on words, performed by transducers with lookahead.
The notable difference is that the nature of the minimal normal form on these transducers is ill adapted to classic RPNI methods, and thus a new normal form has to be found.