Learning Top-Down Tree Transducers with ...
Type de document :
Communication dans un congrès avec actes
Titre :
Learning Top-Down Tree Transducers with Regular Domain Inspection
Auteur(s) :
Boiret, Adrien [Auteur]
Linking Dynamic Data [LINKS]
Lemay, Aurélien [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Linking Dynamic Data [LINKS]
Lemay, Aurélien [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Titre de la manifestation scientifique :
International Conference on Grammatical Inference 2016
Ville :
Delft
Pays :
Pays-Bas
Date de début de la manifestation scientifique :
2016-10-05
Titre de l’ouvrage :
International Conference on Grammatical Inference 2016
Mot(s)-clé(s) en anglais :
Tree Transducers
Myhill-Nerode Theorem
Normal Form
Gold model Learning
Myhill-Nerode Theorem
Normal Form
Gold model Learning
Discipline(s) HAL :
Informatique [cs]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Apprentissage [cs.LG]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Apprentissage [cs.LG]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-01357186/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01357186/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01357186/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- 0.pdf
- Accès libre
- Accéder au document