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.
2000
Pictorial languages; operations on images; decidability; language membership; array grammars
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/47705
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact