Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction

Résumé

To study more formally the approach by reduction initiated by ReGLiS, we propose a formal characterization of the grammars in reduced normal form (RNF) which can be learned by this approach. A modification of the core of ReGLiS is then proposed to ensure returning RNF grammars in polynomial time. This enables us to show that local substitutable languages represented by RNF context-free grammars are identifiable in polynomial time and thick data (IPTtD) from positive examples.
Fichier principal
Vignette du fichier
coste18.pdf (433.12 Ko) Télécharger le fichier
slides-icgi18.pdf (550.9 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01872266 , version 1 (11-09-2018)

Identifiants

  • HAL Id : hal-01872266 , version 1

Citer

François Coste, Jacques Nicolas. Learning local substitutable context-free languages from positive examples in polynomial time and data by reduction. ICGI 2018 - 14th International Conference on Grammatical Inference, Sep 2018, Wrocław, Poland. pp.155 - 168. ⟨hal-01872266⟩
134 Consultations
135 Téléchargements

Partager

Gmail Facebook X LinkedIn More