@article{Průša2016,
title = "Undecidability of the emptiness problem for context-free picture languages ",
journal = "Theoretical Computer Science ",
volume = "",
number = "",
pages = " - ",
year = "2016",
note = "",
issn = "0304-3975",
doi = "http://dx.doi.org/10.1016/j.tcs.2016.03.025",
url = "//www.sciencedirect.com/science/article/pii/S0304397516300147",
author = "Daniel Průša and Klaus Reinhardt",
keywords = "Picture languages",
keywords = "Context-free picture grammars",
keywords = "Emptiness problem",
keywords = "Undecidability ",
abstract = "Abstract 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 → B C , 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. "
}