Distributional Learning of Context-Free Languages under Fixed Finite-Monoid Typing
Dit artikel stelt vast dat contextvrije talen die substitueerbaar zijn onder een vaste eindige-monoïde-typing in de limiet kunnen worden geïdentificeerd uit positieve data, waarbij de constructie en update van hypothesen polynomiale tijd vereisen in de steekproefgrootte voor de algemene vaste-h-klasse, en een volledige polynomiale tijd-en-data-garantie (inclusief een polynomiale bound op de karakteristieke steekproefgrootte) geldt voor de lineaire subclass, via een eindige getypeerde reconstructietheorie die gebruikmaakt van een canonieke hypothese-grammatica die is afgeleid uit een eindige observatieset.