Abstract
As a two-dimensional formal method, graph grammar is widely used in defining various visual programming languages. This paper presents a new graph grammar formalism called coordinate graph ...grammar (CGG). CGG is extended from the edge-based graph grammar (EGG) by introducing the spatial mechanism into the theoretical framework, which consists of continuous coordinate graph grammar (cCGG) and discrete coordinate graph grammar (dCGG). By combining quantitative and qualitative spatial semantics in one framework, CGG provides strong expressiveness and flexibility for specifying various spatial graphs. This paper focuses on several important issues on the new formalism. First, the theoretical framework of CGG is given. Second, two matching algorithms for cCGG and dCGG are proposed, which use the spatial relationships between nodes to narrow down the search space during parsing. Finally, an application of CGG is demonstrated, which generates parsable flowcharts in a uniform layout.
A temporal graph grammar formalism Shi, Zhan; Zeng, Xiaoqin; Zou, Yang ...
Journal of visual languages and computing,
August 2018, 2018-08-00, Letnik:
47
Journal Article
Recenzirano
•We propose a new context-sensitive graph grammar formalism called TEGG in short.•TEGGs introduce some temporal mechanisms in order to tackle time-related issues.•A parsing algorithm for graphs’ ...structure and temporal sequence is presented.•The decidability and complexity of the parsing algorithm are proven.•A case study on an application with temporal requirements is provided.
As a useful formalism tool, graph grammars provide a rigorous but intuitive way to specify visual languages. This paper, based on the existing Edge-based Graph Grammar (EGG), proposes a new context-sensitive graph grammar formalism called the Temporal Edge-based Graph Grammar, or TEGG. TEGG introduces some temporal mechanisms to grammatical specifications, productions, operations and so on in order to tackle time-related issues. In the paper, formal definitions of TEGG are provided first. Then, a new parsing algorithm with a decidability proof is proposed to check the correctness of a given graph's structure, to analyze operations’ timing when needed, and to make the computer simulation of the temporal sequence in the graph available. Next, the complexity of the parsing algorithm is analyzed. Finally, a case study on an application with temporal requirements is provided to show how the parsing algorithm of TEGG works.
Further results of research into graph grammar parsing for syntactic pattern recognition (Pattern Recognit. 21:623-629, 1988; 23:765-774, 1990; 24:1223-1224, 1991; 26:1-16, 1993; 43:249-2264, 2010; ...Comput. Vision Graph. Image Process. 47:1-21, 1989; Fundam. Inform. 80:379-413, 2007; Theoret. Comp. Sci. 201:189-231, 1998) are presented in the paper. The notion of interpreted graphs based on Tarski's model theory is introduced. The bottom-up parsing algorithm for ETPR(k) graph grammars is defined.
On January 18, 2022, around 1 million kilometers from Earth, five times the distance from Earth to the Moon, a large asteroid passed without harm to the Earth. Theoretically, however, the event of ...the asteroid falling into Earth, causing the tsunami, is possible since there are over 27,000 near-Earth asteroids 1, and the Earth’s surface is covered in 71 percent by water. We introduce a novel graph-grammar-based framework for asteroid tsunami simulations. Our framework adaptively generates the computational mesh of the Earth model. It is built from triangular elements representing the seashore and the seabed. The computational mesh is represented as a graph, with graph vertices representing the computational mesh element’s interiors and edges. Mesh refinements are often performed by the longest-edge refinement algorithm. We have expressed this algorithm by only two graph-grammar productions. The resulting graph represents the terrain approximating the topography with a prescribed accuracy. We generalize the graph-grammar mesh refinement algorithm to work on the entire Earth model, allowing the generation of the terrain topography, including the seabed. Having the seashore and the seabed represented by a graph, we introduce the finite element method simulations of the tsunami wave propagation. We illustrate the framework with simulations of the disastrous asteroid falling into the Baltic sea.
•We propose two graph-grammar productions expressing the longest-edge refinement algorithm.•We generate a mesh covering the entire Earth terrain and seabed using our graph-grammar.•We introduce a hyperbolic solver modeling the tsunami propagation.•We derive a detailed mesh of Baltic seabed and seashore using our graph-grammar.•We run the simulations of the asteroid tsunami in the Baltic sea area.
Traditional spatial enabled grammars lack flexibility in specifying the spatial semantics of graphs. This paper describes a new graph grammar formalism called the multigranularity Coordinate Graph ...Grammar (mgCGG) for spatial graphs. Based on the Coordinate Graph Grammar (CGG), the mgCGG divides coordinates into two categories, physical coordinates and grammatical coordinates, where physical coordinates are the common coordinates in the real world, and grammatical coordinates describe the restrictions on the spatial semantics. In the derivation and reduction of the mgCGG, the spatial matching conditions between nodes are evaluated on the basis of the grammatical coordinates, which can be obtained by the specified granularities. By adjusting the granularities, both qualitative and quantitative analyses for spatial semantics can be obtained, including the transition states between them. In addition, a new redex searching algorithm with polynomial time complexity is designed for the mgCGG. A running example of drawing a flowchart is given to illustrate a practical application of the mgCGG. Through a detailed comparison with related spatial-enabled grammars, it is found that the mgCGG has good performance in four critical aspects—the semantics processing mechanism, fault-tolerance, redex searching algorithm, and practical application—providing a flexible yet uniform way to specify spatial graphs and building a bridge between nonspatial and spatial grammars.
Model-based software architecture verification and test scenarios generation are becoming more and more important in the software industry. Based on the existing temporal graph grammar, this paper ...proposes a new formalization method of the context-sensitive graph grammar for aiming at UML activity diagrams, which is called the UML Activity Graph Grammar, or UAGG. In the UAGG, there are new definitions and parsing algorithms. The proposed mechanisms are able to not only check the structural correctness of the UML activity diagram but also automatically generate the test scenario according to user constraints. Finally, a case study is discussed to illustrate how the UAGG and its algorithms work. Keywords: Graph grammar, Parsing algorithm, TEGG, UML
In this paper, we present a method to convert a metamodel in the form of a UML class diagram into a context-sensitive graph grammar whose language comprises precisely the set of model graphs (UML ...object diagrams) that conform to the input metamodel. Compared to other approaches that deal with the same problem, we use a graph grammar formalism that does not employ any advanced graph grammar features, such as application conditions, precedence rules, and production schemes. Specifically, we use Rekers and Schürr’s Layered Graph Grammars, which may be regarded as a pure generalization of standard context-sensitive string grammars. We show that elementary grammatical features, i.e., grammar labels and context-sensitive graph rewrite rules, suffice to represent metamodels with arbitrary multiplicities and inheritance. Inspired by attribute string grammars, we also propose a graph-grammar-based approach to the semantic analysis of model graphs.
In this paper, we present a method that transforms event driven Erlang state machines into high-level state machine models represented in UML. We formalized the transformation system as a triple ...graph grammar, a special case of graph rewriting. We argue in this paper that using this well-defined formal procedure opens up the way for verifying the transformation system, synchronizing code and formal documentation, and executing state machine models among many other possible use cases. We also provide an example transformation system and demonstrate its application in action on a small Erlang state machine. We also present our evaluation of our full system implementation tested on real world Erlang state machines.
•The approach uses load flow principal for automating the design of cable trusses.•Grammar rules use this domain knowledge to quickly find optimal solutions.•Approach and results handle problems with ...multiple loads and supports.•Approach and results address 2D and 3D test problems without increase in the time.•Tree-search algorithm explores design space of many topologies.
This paper describes a generative methodology for optimum design of truss structures. The novelty of the proposed method is its combination of generative design synthesis methods with conventional gradient-based optimization and simulation models. This combination is able to achieve optimal topologies and shapes for cable trusses under various constraints: stress, displacement, stability. Furthermore, manufacturing issues properly limit the generated solutions. A graph grammar is used to define different topologies for a given load problem. The effectiveness of the method is checked by solving a variety of available test problems found in the literature as well as several new three-dimensional solutions.
PDF
