Learning Top-Down Tree Transducers with Regular Domain Inspection

Adrien Boiret 1 Aurélien Lemay 1 Joachim Niehren 1
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We study the problem of how to learn tree transformations on a given regular tree domain from a finite sample of input-output examples. We assume that the target tree transformation can be defined by a deterministic top-down tree transducer with regular domain inspection (DTOPi:reg). An RPNI style learning algorithm that solves this problem in polynomial time and with polynomially many examples was presented at Pods'2010, but restricted to the case of path-closed regular domains. In this paper, we show that this restriction can be removed. For this, we present a new normal form for DTOPi:reg by extending the Myhill-Nerode theorem for DTOP to regular domain inspections in a nontrivial manner. The RPNI style learning algorithm can also be lifted but becomes more involved too.
Keywords : Tree Transducers Myhill-Nerode Theorem Normal Form Gold model Learning
Type de document :
Communication dans un congrès
International Conference on Grammatical Inference 2016, Oct 2016, Delft, Netherlands. International Conference on Grammatical Inference 2016, 〈http://icgi2016.tudelft.nl/〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01357186
Contributeur : Inria Links <>
Soumis le : lundi 29 août 2016 - 14:00:38
Dernière modification le : mardi 3 juillet 2018 - 11:29:14
Document(s) archivé(s) le : mercredi 30 novembre 2016 - 13:58:13

Fichier

0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01357186, version 1

Collections

INRIA | CRISTAL | CRISTAL-LINKS

Citation

Adrien Boiret, Aurélien Lemay, Joachim Niehren. Learning Top-Down Tree Transducers with Regular Domain Inspection. International Conference on Grammatical Inference 2016, Oct 2016, Delft, Netherlands. International Conference on Grammatical Inference 2016, 〈http://icgi2016.tudelft.nl/〉. 〈hal-01357186〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

614

Téléchargements de fichiers

62

Contact


archive-ouverte@inria.fr