Array Grammars with Contextual Operations

Abstract

In this paper, we consider a class of two-dimensional array grammars, called parallel contextual array grammars, that extend the contextual operations on strings to arrays in a naturalway and generate languages of pictures of rectangular arrays. Several classes of these array grammars and the resulting families of picture languages are considered. Necessary conditions for picture languages to be contained in these classes are obtained and the relations between these families are also established.