architecture-1107.pdf (622.6 kB)

Tractable shape grammars

Download (622.6 kB)
journal contribution
posted on 01.04.2013 by Kui Yue, Ramesh Krishnamurti

In this paper we explore the theoretical basis for a concept of ‘computation-friendly’ shape grammars, through a formal examination of tractability of the grammar formalism. Although a variety of shape grammar definitions have evolved over time, it is possible to unify these to be backwards compatible. Under this unified definition, a shape grammar can be constructed to simulate any Turing machine from which it follows that: A shape grammar may not halt; its language space can be exponentially large; and in general, its membership problem is unsolvable. Moreover, parametric subshape recognition is shown to be NP. This implies that it is unlikely, in general, to find a polynomial-time algorithm to interpret parametric shape grammars, and that more pragmatic approaches need to be sought. Factors that influence the tractability of shape grammars are identified and discussed.


Publisher Statement

The final publication is available at Sage via