ON THE POWER OF PICTORIAL LANGUAGES

摘要

We continue the study of pictorial languages as formalized in Ref. 1 (based on the operation of shifting and superposing elementary pictures). If the pixels are superposed without composing their colors, then we produce only recursive languages. When the col- ors 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.