Learning Tree Adjoining Grammars from Structures and Strings


Christophe Costa Florêncio ;
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 \emph{derived trees}. The corresponding strings form a \emph{mildly 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