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.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v21-florencio12a, title = {Learning Tree Adjoining Grammars from Structures and Strings}, author = {Costa Florêncio, Christophe}, booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference}, pages = {129--132}, year = {2012}, editor = {Heinz, Jeffrey and Higuera, Colin and Oates, Tim}, volume = {21}, series = {Proceedings of Machine Learning Research}, address = {University of Maryland, College Park, MD, USA}, month = {05--08 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v21/florencio12a/florencio12a.pdf}, url = {https://proceedings.mlr.press/v21/florencio12a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Learning Tree Adjoining Grammars from Structures and Strings %A Christophe Costa Florêncio %B Proceedings of the Eleventh International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2012 %E Jeffrey Heinz %E Colin Higuera %E Tim Oates %F pmlr-v21-florencio12a %I PMLR %P 129--132 %U https://proceedings.mlr.press/v21/florencio12a.html %V 21 %X 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.
RIS
TY - CPAPER TI - Learning Tree Adjoining Grammars from Structures and Strings AU - Christophe Costa Florêncio BT - Proceedings of the Eleventh International Conference on Grammatical Inference DA - 2012/08/16 ED - Jeffrey Heinz ED - Colin Higuera ED - Tim Oates ID - pmlr-v21-florencio12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 21 SP - 129 EP - 132 L1 - http://proceedings.mlr.press/v21/florencio12a/florencio12a.pdf UR - https://proceedings.mlr.press/v21/florencio12a.html AB - 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. ER -
APA
Costa Florêncio, C.. (2012). Learning Tree Adjoining Grammars from Structures and Strings. Proceedings of the Eleventh International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 21:129-132 Available from https://proceedings.mlr.press/v21/florencio12a.html.

Related Material