Polynomial Time Learner For Inferring Subclasses of Internal Contextual Grammars With Local Maximum Selectors

Abstract

Natural languages contain regular, context-free, and context-sensitive syntactic constructions, yet none of these classes of formal languages can be identified in the limit from positive examples. Mildly context-sensitive languages are capable to represent some context-sensitive constructions such as multiple agreement, crossed agreement, and duplication. These languages are important for natural language applications due to their expressiveness, and the fact that they are not fully context-sensitive. In this paper, we present a polynomial-time algorithm for inferring subclasses of internal contextual languages using positive examples only, namely strictly and k-uniform internal contextual languages with local maximum selectors which can contain mildly context-sensitive languages. © 2017, Springer International Publishing AG.