ON THE POWER OF PICTORIAL LANGUAGES
Paolo Bottoni, Giancarlo Mauri, Piero Mussio, Gheorghe Pǎun · International Journal of Pattern Recognition and Artificial Intelligence · 2000
We continue the study of pictorial languages as formalized in Ref. 1 (based on the operations of shifting and superposing elementary pictures). If the pixels are superposed without composing their colors, then we produce only recursive languages. When the colors of the superposed pixels can be composed, then any array grammar can be simulated (hence, all recursively enumerable languages can be obtained). Bidimensional pictorial frameworks with a nonrecursive membership problem are obtained in the restricted case when (1) we do not allow the superposition of nontransparent pixels, excepting the fact that (2) for each color there is a complementary color, which, superposed on the original one, leads to a transparent pixel.