Design Transformations for Rule‐based Procedural Modeling

We introduce design transformations for rule‐based procedural models, e.g., for buildings and plants. Given two or more procedural designs, each specified by a grammar, a design transformation combines elements of the existing designs to generate new designs. We introduce two technical components to enable design transformations. First, we extend the concept of discrete rule switching to rule merging, leading to a very large shape space for combining procedural models. Second, we propose an algorithm to jointly derive two or more grammars, called grammar co‐derivation. We demonstrate two applications of our work: we show that our framework leads to a larger variety of models than previous work, and we show fine‐grained transformation sequences between two procedural models.     

A Bi‐Directional Procedural Model for Architectural Design

It is a challenge for shape grammars to incorporate spatial hierarchy and interior connectivity of buildings in early design stages. To resolve this difficulty, we developed a bi‐directional procedural model: the forward process constructs the derivation tree with production rules, while the backward process realizes the tree with shapes in a stepwise manner (from leaves to the root). Each inverse‐derivation step involves essential geometric‐topological reasoning. With this bi‐directional framework, design constraints and objectives are encoded in the grammar‐shape translation. We conducted two applications. The first employs geometric primitives as terminals and the other uses previous designs as terminals. Both approaches lead to consistent interior connectivity and a rich spatial hierarchy. The results imply that bespoke geometric‐topological processing helps shape grammar to create plausible, novel compositions. Our model is more productive than hand‐coded shape grammars, while it is less computation‐intensive than evolutionary treatment of shape grammars.     

Shape grammars and shape rules

How to generate various graphics and how to produce patterns automatically according to the ideas, requirements and rules of the people (experts), are quite important problems in the computer aided design (CAD) and design automation (DA). This paper presents an approach, using shape grammars, on the basis of shape rules to design pictures, which is a preliminary practice of solving the problems artificially. SGIS2D-2D shape grammar and shape rule interactive system has been run on IBM3033 mainframe and IBM PC AT with graphic terminal in PASCAL. This practice has shown that rule—based generating graphics is a good design paradigm.     

Shapes and Other Things

Shape grammars have offered a unique computational theory of design over the past forty or so years. Although the focus of shape grammar theory has been on shapes and designs, the material objects or things that might comply with shapes have also been considered. In this paper, I trace the history of approaches for specifying material properties and things through shape grammars. I identify early trends and their limitations, and then propose a new possibility. In early approaches, material things were viewed through the lens of shapes. I argue for a new approach in which shapes are viewed through the lens of material things. Shape grammars are adapted to define making grammars for computing things. Shapes are just one of many things that can be made with these grammars. I conclude with a discussion of the relationship of designing and making, and suggest that designing is a kind of making.     

Graph grammars for evolutionary 3D design

A new interactive evolutionary 3D design system is presented. The representation is based on graph grammars, a fascinating and powerful formalism in which nodes and edges are iteratively rewritten by rules analogous to those of context-free grammars and shape grammars. The nodes of the resulting derived graph are labelled with Euclidean coordinates: therefore the graph fully represents a 3D beam design. Results from user-guided runs are presented, demonstrating the flexibility of the representation. Comparison with results using an alternative graph representation demonstrates that the graph grammar search space is more rich in organised designs. A set of numerical features are defined over designs. They are shown to be effective in distinguishing between the designs produced by the two representations, and between designs labelled by users as good or bad. The features allow the definition of a non-interactive fitness function in terms of proximity to target feature vectors. In non-interactive experiments with this fitness function, the graph grammar representation out-performs the alternative graph representation, and evolution out-performs random search.     

A shape grammar interpreter for rectilinear forms

Shape grammars play an important role in a new generation of tools for the analysis and design of products. Up until now there has been numerous attempts to create a general shape grammar interpreter, but most of the existing tools are either very specific in their purpose, have only limited functionality or were programmed for one operating system. In this work, we present a tool named Shape Grammar Interpreter (SGI) for the automatic generation of designs. The developed shape grammar framework allows designers to automatically synthetize designs and to actively participate in the generation process. Great effort has been devoted to provide an interactive way of defining shapes and later using them in shape grammar rules and designs’ generation process. The tool implements two different types of algorithms for the generation of designs. First, Tree-search algorithms which store the state of the generation process in a tree structure and uses traditional tree-search algorithms to find the next rule to apply. Second, and most importantly, an optimized subshape detection algorithm. Hence, subshapes of the existing shapes can be detected and used in the generation process obtaining not only a wider set of designs but potentially more appealing ones. In this paper, we also describe the architecture of the framework and provide a performance evaluation of proposed algorithms, showing a significant gain in performance. Potential applications of our research can be found in the educational field (i.e. architecture and arts) and in the automatic generation of architectural, mechanical and product designs.     

Simple chain grammars and languages

A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar.Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.     

Graph grammars with neighbourhood-controlled embedding

A central feature that distinguishes graph grammars (we consider grammars generating sets of node-labelled undirected graphs only) from string grammars is that in the former one has to provide a mechanism by which a daughter graph (the right-hand side of a production) can be embedded in the rest of the mother graph, while in the latter this embedding is provided automatically by the structure that all strings possess (left-to-right orientation). In this paper we consider a possible classification of embedding mechanisms for (node-rewriting) graph grammars. This classification originates from the basic ideas of [9]. On the one hand it allows one to fit a number of existing notions of a graph grammar into a common framework and on the other hand it points out new “natural” possibilities for defining the embedding mechanism in a graph grammar. The relationship between the graph-language generating power of graph grammars using various embedding mechanisms is established.     

Forecasting Financial Time Series with Grammar‐Guided Feature Generation

The application of machine learning techniques to forecast financial time series is not a recent development, yet it continues to attract considerable attention because of the difficulty of the problem that is compounded by the nonlinear and nonstationary nature of the time series. The choice of an appropriate set of features is crucial to improve forecasting accuracy of machine learning techniques. In this article, we propose a systematic way for generating rich features using context‐free grammars. Our proposed methodology identifies potential candidates for new technical indicators that consistently improve forecasts compared with some well‐known indicators. The notion of grammar families as a compact representation to generate a rich class of features is exploited, and implementation issues are discussed in detail. The proposed methodology is tested on closing price data of major stock market indices, and the forecasting performance is compared with some standard techniques. A comparison with the conventional approach using standard technical indicators and naive approaches is shown.     

基于神经风格迁移网络的民族图案创新方法

针对传统民族图案符号手工提取效率低,图案组合创新设计困难的问题,以苗族 传统的蜡染和挑花图案创新设计为例提出传统民族图案风格创新模型。该模型将改进型的形状 文法与基于深度学习的神经风格迁移网络相结合,提取并编码民族图案构型框架,通过形状文 法生成大量民族图案构型框架图案,使用风格迁移网络快速提取民族图案中的底层特征,在框 架基础上迁移生成创新民族图案设计方案。实验结果表明,该模型可以在指定框架的基础上生 成全新的民族纹饰图案,相对于直接使用神经网络对空白图像进行风格迁移生成的图案更加有 序。生成图案最终应用于苗族织物图案设计中,验证了该方法和设计流程的可行性。     

The Generating Power of Total Deterministic Tree Transducers

Attributed tree transducers are abstract models used to study properties of attribute grammars. One abstraction which occurs when modeling attribute grammars by attributed tree transducers is that arbitrary trees over a ranked alphabet are taken as input, instead of derivation trees of a context-free grammar. In this paper we show that with respect to the generating power this isnotan abstraction; i.e., we show that attributed tree transducers and attribute grammars generate the same class of term (or tree) languages. To prove this, a number of results concerning the generating power of top-down tree transducers are established, which are interesting in their own. We also show that the classes of output languages of attributed tree transducers form a hierarchy with respect to the number of attributes. The latter result is achieved by proving a hierarchy of classes of tree languages generated by context-free hypergraph grammars with respect to their rank.     

A Virtual World Grammar for automatic generation of virtual worlds

Hybrid systems such as those that combine 3D virtual worlds and organization based multiagent systems add new visual and communication features for multiuser applications. The design of such hybrid and dynamic systems is a challenging task. In this paper, we propose a system that can automatically generate a 3D virtual world (VW) from an organization based multiagent system (MAS) specification that establishes the activities participants can engage on. Both shape grammar and virtual world paradigms inspired us to propose a Virtual World Grammar (VWG) to support the generation process of a virtual world design. A VWG includes semantic information about both MAS specification and shape grammar elements. This information, along with heuristics and validations, guides the VW generation producing functional designs. To support the definition and execution of a Virtual World Grammar, we have developed a so named Virtual World Builder Toolkit (VWBT). We illustrate this process by generating a 3D visualization of a virtual institution from its specification.     

Context-free like restrictions on selective rewriting

Selective substitution grammars based on ‘context-free’ productions form a possible framework for the study of ‘grammatically oriented’ formal language theory. Such grammars (with no control governing the composition of derivation steps) are studied in this paper. In particular we study the effect of various conditions on selectors (which define the way that rewriting is performed); those conditions are aimed to formalize the notion of ‘using information about the context’ during the rewriting process. Each of them captures a particular feature of a rewriting according to a context-free grammar or an EOS system (essentially a context-free grammar that can also rewrite terminal symbols). Some of those conditions yield characterizations of the class of context-free languages for other conditions the lower and upper bound on the language generating power are given. Also a natural notion of a class of ‘simple’ rewriting systems is introduced (pattern grammars) and it is demonstrated that they possess surprisingly high language generating power.     

Chinese lattice designs and parametric shape grammars

Chinese lattice designs are a rich source of interesting geometric forms. We describe a parametric shape grammar that generates ice-ray lattices. We also provide an overview of shape grammars — formal, graphical production systems that perform graphical computations with parametric labeled shapes (finite arrangements of nonzero line segments with a finite set of labeled points).     

Analyzing ambiguity of context-free grammars

It has been known since 1962 that the ambiguity problem for context-free grammars is undecidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammar ambiguity problem, and we show how to exploit this by presenting an ambiguity analysis framework based on conservative language approximations. As a concrete example, we propose a technique based on local regular approximations and grammar unfoldings. We evaluate the analysis using grammars that occur in RNA analysis in bioinformatics, and we demonstrate that it is sufficiently precise and efficient to be practically useful.     

Parameter-reduction of higher level grammars

A higher level (OI-) grammar is called terminating if for every accessible term t there is at least one terminal term which can be derived from t. A grammar is called parameter-reduced if it is terminating and has no superfluous parameters. For every grammar G of level n0 which generates at least one term we construct grammars R(G) and P(G) such that R(G) and P(G) generate the same language as G but are terminating and parameter-reduced respectively. We introduce a hierarchy of restrictions to the delection capability of the grammars which allow a gradual decrease in the complexity of the algorithms from n-iterated exponential time to polynomial time.     

Using Meta-Modelling and Graph Grammars to Create Modelling Environments

This paper presents the combined use of meta-modelling and graph grammars for the generation of visual modelling tools for simulation formalisms. In meta-modelling, formalisms are described at a meta-level. This information is used by a meta-model processor to generate modelling tools for the described formalisms. We combine meta-modelling with graph grammars to extend the model manipulation capabilities of the generated modelling tools, as we store (meta-)models as graphs, and thus, express model manipulations as graph grammars.We show the design and implementation of these concepts in AToM³ (A Tool for Multi-formalism, Meta-Modelling). As an example we will present a meta-model for Causal Block Diagrams and a graph grammar to generate OOCSMP code, a continuous simulation language which has a compiler able to generate Java applets from the simulations models.     

Approximation of fuzzy context-free grammars

Fuzzy context-free max- grammar (or FCFG, for short), as a straightforward extension of context-free grammar, has been introduced to express uncertainty, imprecision, and vagueness in natural language fragments. Li recently proposed the approximation of fuzzy finite automata, which may effectively deal with the practical problems of fuzziness, impreciseness and vagueness. In this paper, we further develop the approximation of fuzzy context-free grammars. In particular, we show that a fuzzy context-free grammar under max- compositional inference can be approximated by some fuzzy context-free grammar under max-min compositional inference with any given accuracy. In addition, some related properties of fuzzy context-free grammars and fuzzy languages generated by them are studied. Finally, the sensitivity of fuzzy context-free grammars is also discussed.     

Supporting design through the strategic use of shape grammars

This paper is concerned with the early processes of design, particularly in the context of spatial arrangements. We are interested in the strategies that a designer uses in order to achieve success and with the opportunities that might exist for computer support. The technical device that provides the focus for the work is the concept of a shape grammar. The investigation that has taken place has looked at certain opportunities that might exist for building support systems employing shape grammars and the implications that they might have for the strategic level of design. From the exploration we conclude that the use of shape grammars to expand the strategies available to a designer and to provide computational support for exploring the implications of employing given sets of design rules is promising. Moreover, we have already identified a number of directions in which the research should be taken further.