We continue the study of pictorial languages 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 non recursive membership problem are obtained in the restricted case when (1) we do not allow the superposition of non transparent 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
Bottoni, P., Mauri, G., Mussio, P., Paun, G. (2000). On the power of pictorial languages. INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 14(6), 839-858 [10.1142/S0218001400000453].
On the power of pictorial languages
MAURI, GIANCARLO;
2000
Abstract
We continue the study of pictorial languages 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 non recursive membership problem are obtained in the restricted case when (1) we do not allow the superposition of non transparent 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.
