Back to Search
Start Over
Tractable shape grammars.
- Source :
-
Environment & Planning B: Planning & Design . Jul2013, Vol. 40 Issue 4, p576-594. 19p. - Publication Year :
- 2013
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02658135
- Volume :
- 40
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Environment & Planning B: Planning & Design
- Publication Type :
- Academic Journal
- Accession number :
- 90116960
- Full Text :
- https://doi.org/10.1068/b38227