Learning Tree Adjoining Grammars from Structures and Strings
Christophe Costa Florêncio · 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 derived trees. The corresponding strings form a 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.