Tractable shape grammars
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. <br> <b>Keywords:</b> shape grammar definitions, Turing machine, parametric shape recognition, computational complexity, tractability
Year of publication: |
2013
|
---|---|
Authors: | Yue, Kui ; Krishnamurti, Ramesh |
Published in: |
Environment and Planning B: Planning and Design. - Pion Ltd, London, ISSN 1472-3417. - Vol. 40.2013, 4, p. 576-594
|
Publisher: |
Pion Ltd, London |
Saved in:
freely available
Saved in favorites
Similar items by person
-
A paradigm for interpreting tractable shape grammars
Yue, Kui, (2014)
-
A heuristic approach to product design
Kohli, Rajeev, (1987)
-
Optimal production design using conjoint analysis : computational complexity and algorithms
Kohli, Rajeev, (1989)
- More ...