Affiliations: [a] Department of Philosophy, King’s College London, UK. alexander.clark@kcl.ac.uk | [b] National Institute of Informatics, Tokyo, Japan. kanazawa@nii.ac.jp | [c] Department of Linguistics and Computation Institute, University of Chicago, USA. kobele@uchicago.edu | [d] Graduate School of Informatics, Kyoto University, Japan. ry@i.kyoto-u.ac.jp
Correspondence:
[†]
Address for correspondence: National Institute of Informatics, Tokyo. Also works: SOKENDAI (Graduate University for Advanced Studies)
Note: [*] This work was supported by NII joint research project “Algorithmic Learning of Nonlinear Formalisms Based on Distributional Learning”.
Note: [‡] Ryo Yoshinaka’s work was supported in part by JSPS KAKENHI Grant Numbers 24106010, 26330013.
Abstract: A key component of Clark and Yoshinaka’s distributional learning algorithms is the extraction of substructures and contexts contained in the input data. This problem often becomes intractable with nonlinear grammar formalisms due to the fact that more than polynomially many substructures and/or contexts may be contained in each object. Previous works on distributional learning of nonlinear grammars avoided this difficulty by restricting the substructures or contexts that are made available to the learner. In this paper, we identify two classes of nonlinear tree grammars for which the extraction of substructures and contexts can be performed in polynomial time, and which, consequently, admit successful distributional learning in its unmodified, original form.
Keywords: Distributional learning, tree language, tree pattern, generalized context-free grammar, parallel regular tree grammar, IO context-free tree grammar
