Learning Tree Adjoining Grammars from Structures and Strings


Christophe Costa Flor, ecircncio ;
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:129-132, 2012.


We investigate the learnability of certain subclasses of tree adjoining grammars (TAGs). TAGs are based on two tree-tree operations, and generate structures known as \emphderived trees. The corresponding strings form a \emphmildly context-sensitive language. We prove that even very constrained subclasses of TAGs are not learnable from structures (derived trees) or strings, demonstrating that this type of problem is far from trivial. We also demonstrate that a large (parameterized) family of classes of TAGs is learnable from strings.

Related Material