Polynomial Time Algorithm For Inferring Subclasses of Parallel Internal Column Contextual Array Languages

Abstract

In [2,16] a new method of description of pictures of digitized rectangular arrays is introduced based on contextual grammars, called parallel internal contextual array grammars. In this paper, we pay our attention on parallel internal column contextual array grammars and observe that the languages generated by these grammars are not inferable from positive data only. We define two subclasses of parallel internal column contextual array languages, namely, k-uniform and strictly parallel internal column contextual languages which are incomparable and not disjoint classes and provide identification algorithms to learn these classes. © Springer International Publishing AG 2017.