We apply basic notions of the theory of rough sets, due to Pawlak [30, 31], to explicate certain properties of unification-based learning algorithms for categorial grammars, introduced in [6, 11] and further developed in e.g. [18, 19, 24, 25, 26, 9, 28, 14, 15, 3]. The outcomes of these algorithms can be used to compute both the lower and the upper approximation of the searched language with respect to the given, finite sample. We show that these methods are also appropriate for other kinds of formal grammars, e.g. context-free grammars and context-sensitive grammars.
Journal description