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

François Coste 1 Jacques Nicolas 2
1 Dyliss - Dynamics, Logics and Inference for biological Systems and Sequences
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
2 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : 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.
Keywords : Learnability Substitutable languages Context-free grammars Normal form
Document type :
Conference papers
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download
https://hal.inria.fr/hal-01872266
Contributor : François Coste <>
Submitted on : Tuesday, September 11, 2018 - 6:07:40 PM
Last modification on : Friday, September 13, 2019 - 9:49:21 AM
Long-term archiving on: Wednesday, December 12, 2018 - 3:45:27 PM

Files

coste18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01872266, version 1

Collections

UNIV-RENNES1 | UNIV-RENNES | CENTRALESUPELEC | IRISA | INRIA | CNRS | UR1-UFR-ISTIC

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

123

Files downloads

85

 

 

Contact

archive-ouverte@inria.fr