{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:42:17Z","timestamp":1767339737130,"version":"3.37.3"},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2018,5,9]],"date-time":"2018-05-09T00:00:00Z","timestamp":1525824000000},"content-version":"unspecified","delay-in-days":8,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIEDAM"],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computer-based shape grammar implementations aim to support creative design exploration by automating rule-application. This paper reviews existing shape grammar implementations in terms of their algorithmic complexity, extends the definition of shape grammars with sets of transformations for rule application, categorizes (parametric and non-parametric) sets of transformations, and analyses these categories in terms of the resulting algorithmic complexity. Specifically, it describes how different sets of transformations admit different numbers of targets (i.e., potential inputs) for rule application. In the non-parametric case, this number is quadratic or cubic, while in the parametric case, it can be non-polynomial, depending on the size of the target shape. The analysis thus yields lower bounds for the algorithmic complexity of shape grammar implementations that hold independently of the employed algorithm or data structure. Based on these bounds, we propose novel matching algorithms for non-parametric and parametric shape grammar implementation and analyze their complexity. The results provide guidance for future, general-purpose shape grammar implementations for design exploration.<\/jats:p>","DOI":"10.1017\/s0890060417000440","type":"journal-article","created":{"date-parts":[[2018,5,9]],"date-time":"2018-05-09T03:35:59Z","timestamp":1525836959000},"page":"138-146","source":"Crossref","is-referenced-by-count":12,"title":["Algorithmic complexity of shape grammar implementation"],"prefix":"10.1017","volume":"32","author":[{"given":"Thomas","family":"Wortmann","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4200-5833","authenticated-orcid":false,"given":"Rudi","family":"Stouffs","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,5,9]]},"reference":[{"key":"S0890060417000440_ref36","doi-asserted-by":"publisher","DOI":"10.1068\/b38227"},{"key":"S0890060417000440_ref35","unstructured":"Wortmann T (2013) Representing Shapes as Graphs, SMArchS Thesis. Cambridge, MA: Massachusetts Institute of Technology."},{"key":"S0890060417000440_ref20","doi-asserted-by":"publisher","DOI":"10.1068\/b170097"},{"key":"S0890060417000440_ref23","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6201.001.0001","volume-title":"Shape: talking about seeing and doing","author":"Stiny","year":"2006"},{"key":"S0890060417000440_ref22","doi-asserted-by":"publisher","DOI":"10.1068\/b21s049"},{"key":"S0890060417000440_ref19","doi-asserted-by":"publisher","DOI":"10.1068\/b080257"},{"key":"S0890060417000440_ref16","unstructured":"Sloane NJA and Arndt J (eds) (2010) The On-Line Encyclopedia of Integer Sequences. Available online at https:\/\/oeis.org"},{"key":"S0890060417000440_ref13","doi-asserted-by":"publisher","DOI":"10.1068\/b240359"},{"key":"S0890060417000440_ref11","doi-asserted-by":"publisher","DOI":"10.2307\/1575896"},{"key":"S0890060417000440_ref10","doi-asserted-by":"publisher","DOI":"10.1068\/b160417"},{"key":"S0890060417000440_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01901028"},{"key":"S0890060417000440_ref4","unstructured":"Dorn F (2010) Planar subgraph isomorphism revisited. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science."},{"volume-title":"Introduction to Algorithms","year":"2009","author":"Cormen","key":"S0890060417000440_ref3"},{"key":"S0890060417000440_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-2393-4_19"},{"key":"S0890060417000440_ref26","doi-asserted-by":"publisher","DOI":"10.1068\/b050005"},{"key":"S0890060417000440_ref30","doi-asserted-by":"publisher","DOI":"10.1504\/JDR.2006.010796"},{"key":"S0890060417000440_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0795-4_6"},{"key":"S0890060417000440_ref8","unstructured":"Gips J (1999) Computer implementation of shape grammars. NSF\/MIT Workshop on Shape Computation."},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey","key":"S0890060417000440_ref7"},{"key":"S0890060417000440_ref18","doi-asserted-by":"publisher","DOI":"10.1068\/b070343"},{"key":"S0890060417000440_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S0890060417000270"},{"key":"S0890060417000440_ref1","unstructured":"Batz GV (2006) An Optimization Technique for Subgraph Matching Strategies (Internal Report No. 7). Institut f\u00fcr Programmstrukturen und Datenorganisation, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe (TH), DE."},{"key":"S0890060417000440_ref37","doi-asserted-by":"publisher","DOI":"10.1068\/b39107"},{"key":"S0890060417000440_ref6","doi-asserted-by":"crossref","unstructured":"Frank AU (1999) One step up the abstraction ladder: Combining algebras-from functional pieces to a whole. In Proceedings of the International Conference on Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science. London, UK: Springer.","DOI":"10.1007\/3-540-48384-5_7"},{"key":"S0890060417000440_ref25","doi-asserted-by":"publisher","DOI":"10.1068\/b050189"},{"key":"S0890060417000440_ref33","doi-asserted-by":"publisher","DOI":"10.1068\/b260059"},{"key":"S0890060417000440_ref5","unstructured":"Duarte JP (2001) Customizing Mass Housing: A Discursive Grammar for Siza's Malagueira Houses, Ph.D. Dissertation. Boston, MA: Massachusetts Institute of Technology."},{"key":"S0890060417000440_ref9","doi-asserted-by":"publisher","DOI":"10.1068\/b38156"},{"key":"S0890060417000440_ref14","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00094"},{"key":"S0890060417000440_ref12","doi-asserted-by":"publisher","DOI":"10.1068\/b080005"},{"key":"S0890060417000440_ref15","first-page":"25","volume-title":"Modeling Creativity and Knowledge-Based Creative Design","author":"Mitchell","year":"1993"},{"key":"S0890060417000440_ref27","doi-asserted-by":"crossref","unstructured":"Stouffs R (2017) A practical shape grammar for Chinese ice-ray lattice designs. In Cultural DNA Workshop: Computational studies on the cultural variation and heredity. Daejeon, KR.","DOI":"10.1007\/978-981-10-8189-7_13"},{"key":"S0890060417000440_ref17","doi-asserted-by":"publisher","DOI":"10.1068\/b040089"},{"key":"S0890060417000440_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.02.009"},{"key":"S0890060417000440_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0890060415000475"},{"key":"S0890060417000440_ref21","doi-asserted-by":"publisher","DOI":"10.1068\/b190413"},{"key":"S0890060417000440_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00004-011-0056-6"}],"container-title":["Artificial Intelligence for Engineering Design, Analysis and Manufacturing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0890060417000440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,17]],"date-time":"2019-10-17T15:39:07Z","timestamp":1571326747000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0890060417000440\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["S0890060417000440"],"URL":"https:\/\/doi.org\/10.1017\/s0890060417000440","relation":{},"ISSN":["0890-0604","1469-1760"],"issn-type":[{"type":"print","value":"0890-0604"},{"type":"electronic","value":"1469-1760"}],"subject":[],"published":{"date-parts":[[2018,5]]}}}