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.
On the Power of Pictorial Languages / Bottoni, Paolo Gaspare; G., Mauri; P., Mussio; G., Paun. - In: INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE. - ISSN 0218-0014. - STAMPA. - 14:(2000), pp. 839-858. [10.1142/S0218001400000453]
On the Power of Pictorial Languages
BOTTONI, Paolo Gaspare;
2000
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.