Criteria to disprove context freeness of collage languages

✍ Scribed by Frank Drewes; Hans-Jörg Kreowski; Denis Lapoire

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 262 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00049-x

✦ Synopsis

Collage grammars are context-free devices which generate picture languages consisting of collages-sets of parts, where a part is a set of points in a given space. In order to show that certain collage languages cannot be generated, the well-known pumping technique turns out to be rather useless. To circumvent this di culty, other necessary criteria for context-freeness are established in this paper. Roughly speaking, these criteria reveal that (1) the collages in a context-free collage language can be de ated stepwise in such a manner that the di erence between subsequent collages in the resulting chain is small and (2) the volume of parts can grow or shrink only exponentially.