Tractable Shape Grammars

Kui Yue and Ramesh Krishnamurti
Additional contact information
Kui Yue: Microsoft, Redmond, WA 98052, USA
Ramesh Krishnamurti: Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA

Environment and Planning B, 2013, vol. 40, issue 4, 576-594

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.

Keywords: shape grammar definitions; Turing machine; parametric shape recognition; computational complexity; tractability (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1068/b38227 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:envirb:v:40:y:2013:i:4:p:576-594

DOI: 10.1068/b38227

Access Statistics for this article

More articles in Environment and Planning B
Bibliographic data for series maintained by SAGE Publications ().