This paper deals with a multi-agent system which supports the designer in solving complex design tasks. The behaviour of design agents is modelled by sets of grammar rules. Each agent uses a graph ...grammar or a shape grammar and a database of facts concerning the subtask it is responsible for. The course of the design process is determined by the interaction between specialised agents. Space layouts of designs are represented by attributed graphs encoding both topological structures and semantic properties of solutions. The agents work in parallel on the common graph, independently generating layouts of different design components while specified node labels evoke agents using shape grammars. The agents’ cooperation allows them to combine a form-oriented approach with a functional-structural one in the design process, where the agents generate the general 3D form of the object based on design requirements together with the space layout based on the functional aspects of the solution. Based on the given design criteria, the agents search for admissible solutions within the design space that constitutes their operating environment. The proposed approach is illustrated by the example of designing kindergarten facilities.
Virtualization technology allows service providers to operate data centers in a cost-effective and scalable manner. The data center network (substrate network) and the applications executed in the ...data center (virtual networks) are often modeled as graphs. The nodes of the graphs represent (physical or virtual) servers and switches, and the edges represent communication links. Nodes and links are annotated with the provided and required resources (e.g., memory and bandwidth). The NP-hard virtual network embedding (VNE) problem deals with the embedding of a set of virtual networks to the substrate network such that (i) all (resource) constraints of the substrate network are fulfilled, and (ii) an objective is optimized (e.g., minimizing the communication costs). The existing two-step highly customizable model-driven virtual network embedding (MdVNE) approach combines model transformation (MT) and integer linear programming (ILP) techniques to solve the VNE problem based on a declarative specification. MdVNE generates element mapping candidates from an MT specification and identifies an optimal and correct embeddings using an ILP solver. In the past, developers created the MT and ILP specifications manually and needed to ensure carefully that both are compatible and respect the problem description. In this article, we present a novel construction methodology for synthesizing the MT and ILP specification from a given declarative model-based VNE problem description. This problem description consists of a metamodel for substrate and virtual networks, additional OCL constraints, and an objective function that assigns costs to a given model. This methodology ensures that the derived embeddings are correct w.r.t. the metamodel and the OCL constraints, and optimal w.r.t. the optimization goal. The novel model-based VNE specification is applicable to different network domains, environments, and constraints. Thus, the construction methodology allows to automate most of the steps to realize a correct and optimal VNE algorithm compared to a hand-crafted VNE implementation. Furthermore, the simulative evaluation confirms that using MT techniques reduces the time for solving the VNE problem considerably in comparison with a purely ILP-based approach.
This article reviews grammatical formalisms that are capable of supporting spatial specification and reasoning, or spatial-enabled grammars, and their wide range of applications. The review takes two ...typical grammars, i.e., shape grammar and spatial graph grammar, as concrete representatives to consider connectivity and spatial relations in the parsing and generating processes. This article proposes four aspects as a set of criteria to compare the commonality and differences among spatial-enabled grammars, i.e., parsing and generation, granularity of spatial specification, form of spatial specification, and 2D and 3D modeling. Finally, further developments related to spatial-enabled grammars are discussed.
Adaptive star grammars and their languages Drewes, Frank; Hoffmann, Berthold; Janssens, Dirk ...
Theoretical computer science,
07/2010, Letnik:
411, Številka:
34
Journal Article
Recenzirano
Odprti dostop
Motivated by applications that require mechanisms for describing the structure of object-oriented programs, adaptive star grammars are introduced, and their fundamental properties are studied. In ...adaptive star grammars, rules are actually schemata which, via the cloning of so-called multiple nodes, may adapt to potentially infinitely many contexts when they are applied. This mechanism makes adaptive star grammars more powerful than context-free graph grammars. Nevertheless, they turn out to be restricted enough to share some of the basic characteristics of context-free devices. In particular, the underlying substitution operator enjoys associativity and confluence properties quite similar to those of context-free graph grammars, and the membership problem for adaptive star grammars is decidable.
Introduction
Tandem mass spectrometry (MS/MS) has been widely used for identifying metabolites in many areas. However, computationally identifying metabolites from MS/MS data is challenging due to ...the unknown of fragmentation rules, which determine the precedence of chemical bond dissociation. Although this problem has been tackled by different ways, the lack of computational tools to flexibly represent adjacent structures of chemical bonds is still a long-term bottleneck for studying fragmentation rules.
Objectives
This study aimed to develop computational methods for investigating fragmentation rules by analyzing annotated MS/MS data.
Methods
We implemented a computational platform, MIDAS-G, for investigating fragmentation rules. MIDAS-G processes a metabolite as a simple graph and uses graph grammars to recognize specific chemical bonds and their adjacent structures. We can apply MIDAS-G to investigate fragmentation rules by adjusting bond weights in the scoring model of the metabolite identification tool and comparing metabolite identification performances.
Results
We used MIDAS-G to investigate four bond types on real annotated MS/MS data in experiments. The experimental results matched data collected from wet labs and literature. The effectiveness of MIDAS-G was confirmed.
Conclusion
We developed a computational platform for investigating fragmentation rules of tandem mass spectrometry. This platform is freely available for download.
Automatically constructing analog circuit topology according to specifications is always a challenging task, due to the high complexity and substantial design expertise required. This paper proposes ...a graph-grammar-based method that can efficiently and automatically generate analog circuit topologies, which can be applied to general analog circuit synthesis frameworks for analog circuit design. The topology generation process is encoded by constructing a binary tree, in which the leaf nodes are decomposed according to a set of grammar rules. In order to guarantee only unique circuit structures to be generated, double isomorphism checks are applied at both tree structure level and circuit transistor level. Our experimental results demonstrate the high efficiency and wide applicability of the proposed method.
The representation and recognition of complex semantic events (e.g. illegal parking, stealing objects) is a challenging task for high-level understanding of video sequence. To solve this problem, an ...attribute graph grammar for events modeling is studied in this paper. This grammar models the variability of semantic events by a set of meaningful “event components” with the spatio-temporal constraints. The event components are defined manually according to their semantic meaning, and further decomposed into atomic event primitives. These event primitives are learned on a object-trajectory table that describes mobile object attributes (location, velocity, and visibility) in a video sequence. A dictionary of temporal and spatial relations are defined to constrain the event primitives. With this representation, one observed event can be parsed into an “event parse graph”, and all possible variability of one event can be modeled into an “event And–Or graph”, in a syntactic way. The probability model of an “event And–Or graph” can be learned on a set of annotated event instances, and given a learned event And–Or graph, a Gibbs sampling scheme is utilized for inference on a testing video. In the experiments, we test events recognition performance of the proposed on both real indoor and outdoor videos and show quantitative recognition rate on the public LHI dataset.
The use of grammars in design and analysis has been set back by the lack of automated ways to induce them from arbitrarily structured datasets. Machine translation methods provide a construct for ...inducing grammars from coded data which have been extended to be used for design through pre-coded design data. This work introduces a four-step process for inducing grammars from un-coded structured datasets which can constitute a wide variety of data types, including many used in the design. The method includes: (1) extracting objects from the data, (2) forming structures from objects, (3) expanding structures into rules based on frequency, and (4) finding rule similarities that lead to consolidation or abstraction. To evaluate this method, grammars are induced from generated data, architectural layouts and three-dimensional design models to demonstrate that this method offers usable grammars automatically which are functionally similar to grammars produced by hand.
Background and AimsFunctional–structural plant models (FSPMs) simulate biological processes at different spatial scales. Methods exist for multiscale data representation and modification, but the ...advantages of using multiple scales in the dynamic aspects of FSPMs remain unclear. Results from multiscale models in various other areas of science that share fundamental modelling issues with FSPMs suggest that potential advantages do exist, and this study therefore aims to introduce an approach to multiscale modelling in FSPMs.MethodsA three-part graph data structure and grammar is revisited, and presented with a conceptual framework for multiscale modelling. The framework is used for identifying roles, categorizing and describing scale-to-scale interactions, thus allowing alternative approaches to model development as opposed to correlation-based modelling at a single scale. Reverse information flow (from macro- to micro-scale) is catered for in the framework. The methods are implemented within the programming language XL.Key ResultsThree example models are implemented using the proposed multiscale graph model and framework. The first illustrates the fundamental usage of the graph data structure and grammar, the second uses probabilistic modelling for organs at the fine scale in order to derive crown growth, and the third combines multiscale plant topology with ozone trends and metabolic network simulations in order to model juvenile beech stands under exposure to a toxic trace gas.ConclusionsThe graph data structure supports data representation and grammar operations at multiple scales. The results demonstrate that multiscale modelling is a viable method in FSPM and an alternative to correlation-based modelling. Advantages and disadvantages of multiscale modelling are illustrated by comparisons with single-scale implementations, leading to motivations for further research in sensitivity analysis and run-time efficiency for these models.
VPPE: A Novel Visual Parallel Programming Environment Quiroz-Fabián, José L.; Román-Alonso, Graciela; Castro-García, Miguel A. ...
International journal of parallel programming,
12/2019, Letnik:
47, Številka:
5-6
Journal Article
Recenzirano
Parallel programming continues to be a challenging task despite the many advances in parallel architectures and their wide availability in the cloud. The need both to partition the workload among ...various processing elements and to specify communication between them to share code and data, and to coordinate their tasks, requires from the developer a deep understanding of the problem, the parallel architecture and the programming language used in order to develop efficient parallel applications. This problem can be reduced significantly through the use of visual programming languages to hide most aspects related to the specification of communication and processes management. This paper presents VPPE, a novel Visual Parallel Programming Environment that allows developers to program parallel applications through organising workflows of interconnected icons. VPPE is a cloud environment that supports icons for specifying: I/O operations, workflow organisation, communication, and processing. Processing computing patterns supported so far include Single Program Multiple Data, Multiple Program Multiple Data, Pipeline, and Master–Slave. The paper highlights the design of VPPE based on a context-free graph grammar, its current implementation based on Java-MPI, its use in developing various parallel applications, and its evaluation compared to Java-MPI text-based programming.
PDF
