Undecidability of the emptiness problem for context-free picture languages

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00312203" target="_blank" >RIV/68407700:21230/17:00312203 - isvavai.cz</a>
Result on the web
<a href="http://www.sciencedirect.com/science/article/pii/S0304397516300147" target="_blank" >http://www.sciencedirect.com/science/article/pii/S0304397516300147</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2016.03.025" target="_blank" >10.1016/j.tcs.2016.03.025</a>

Result language
angličtina
Original language name
Undecidability of the emptiness problem for context-free picture languages
Original language description
A two-dimensional Kolam grammar as defined by Siromoney et al. in 1972 and independently by Matz in 1997 and Schlesinger in 1989 allows context-free productions of the form A->a, A->BC, A->B/C, and S->λ which concatenate sub-pictures produced by B and C horizontally respectively vertically if their height respectively width fits. We demonstrate that this grammar is quite powerful by proving undecidability of the emptiness problem. We further analyze consequences of this finding and give additional characteristics related to size of generated pictures.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - Structures, Learning and Cognition</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)