Narrow Results

The emptiness problem for non-overlapping Basic puzzle grammars is shown to be decidable. An alternate proof of the decidability of the non-overlapping feature for basic puzzle grammars is given. Hierarchy among the various classes of puzzle languages is also established.

The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho, is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results, applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.