Table-Driven and Context-Sensitive Collage Languages

In this paper, we introduce the notions of context-sensitive and ET0L collage grammars as generalizations of context-free collage grammars. Both kinds of picture-generating devices are more powerful than the context-free case. Nevertheless, the size of collages in an ET0L collage language can be shown to grow at most exponentially. In contrast to this, there are no such bounds for context-sensitive collage languages because suitable pictorial representations of recursively enumerable sets of strings can be generated. On the other hand, it is still a conjecture that ET0L collage languages exist that are not context-sensitive.