Distributional Learning of Context-Free Languages under Fixed Finite-Monoid Typing
Questo articolo stabilisce che i linguaggi context-free sostituibili sotto una tipizzazione finita di monoidi fissata possono essere identificati al limite da dati positivi, con la costruzione e l'aggiornamento dell'ipotesi che richiedono tempo polinomiale rispetto alla dimensione del campione per la classe generale fixed-h, mentre viene garantita una piena efficienza temporale e di dati (incluso un limite polinomiale sulla dimensione del campione caratteristico) per la sottoclasse lineare, sviluppando una teoria di ricostruzione tipata finita che utilizza una grammatica di ipotesi canonica derivata da un insieme finito di osservazioni.