OGDEN'S LEMMA FOR SUBCLASSES OF RANDOM CONTEXT GALLERIES.

Random context picture grammars are used to generate pictures through successive refinement. There exist several subclasses of these grammars, e. g., context-free picture grammars, random permitting context picture grammars, random forbidding context picture grammars and table-driven context-free picture grammars. These classes generate context-free galleries (cfpls), random permitting context galleries (rPcpls), random forbidding context galleries (rFcpls) and table-driven context-free galleries (Tcfpls), respectively. For all these classes of galleries, necessary conditions have been proven. In particular, for cfpls, there exists a pumping-shrinking lemma, for rPcpls, a pumping lemma and for rFcpls, a shrinking lemma. For Tcfpls, two necessary conditions have been proven. Recently, a new necessary condition related to the size of a subpicture was proven for each of the abovementioned classes of galleries. We now prove theorems that are an alternative to the existing necessary conditions. This is done by adapting Ogden's idea of marking parts of a word for the picture case. We illustrate the new conditions with examples. For rPcpls and Tcfpls, we also give examples of galleries for which the marking is necessary. [ABSTRACT FROM AUTHOR]