Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952139 | Theoretical Computer Science | 2017 | 8 Pages |
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âBC, AâBC, 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Průša, Klaus Reinhardt,