Learning Mildly Context-Sensitive Languages with Multidimensional Substitutability from Positive Data

摘要

Recently Clark and Eyraud (2007) have shown that sub-stitutable 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 mildly context-sensitive languages with variants of substitutability.