On the power of pictorial languages

Citation
P. Bottoni et al., On the power of pictorial languages, INT J PATT, 14(6), 2000, pp. 839-858
Citations number
18
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE
ISSN journal
02180014 → ACNP
Volume
14
Issue
6
Year of publication
2000
Pages
839 - 858
Database
ISI
SICI code
0218-0014(200009)14:6<839:OTPOPL>2.0.ZU;2-X
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 compo sed, then any array grammar can be simulated (hence, all recursively enumer able 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, superp osed on the original one, leads to a transparent pixel.