Efficient learning of multiple context-free languages with multidimensional substitutability from positive data

Recently Clark and Eyraud (2007) 10] have shown that substitutable context-free languages, which capture an aspect of natural language phenomena, are efficiently identifiable in the limit from positive data. Generalizing their work, this paper presents a polynomial-time learning algorithm for new subclasses of multiple context-free languages with variants of substitutability.