Finding useful information from the Web becomes increasingly difficult as the volume of Web data rapidly grows. To facilitate effective Web browsing, Web designers usually display the same type of ...information with a consistent layout (referred to as a Web pattern). Discovering Web patterns can benefit many applications, such as extracting structured data. This paper presents a generic framework for discovering Web patterns and recognizing their instances (i.e., structured data) based on graph grammars. In our framework, a Web pattern is visually yet formally specified as a graph grammar, which is automatically induced through a grammar induction engine. The grammar induction engine is featured by converting the problem of (2-dimensional) graph grammar induction to (1-dimensional) string induction. Based on the induced pattern, matching instances are recognized from Web pages through a graph parsing process. We have evaluated the framework on twenty-one e-commerce Web sites. The evaluation results are promising with a high F1-score.
Abstract Graph-based semantic representations are popular in natural language processing, where it is often convenient to model linguistic concepts as nodes and relations as edges between them. ...Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but that context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
This paper deals with supporting the design of building floor plans. Floor layouts are represented by labelled and attributed graphs. These graphs are generated using graph grammars, i.e., systems ...for transforming graphs according to specified rules. The key feature of a graph grammar is that graph representations are obtained by successively adding nodes and edges by applying the rules during the generation process with the use of the so-called embedding principle. The existing embedding principles are often not sufficient to create solutions which fulfill the design criteria. The main contribution of this paper is a generative graph grammar with an innovative semantic-driven embedding where graph attribute values are taken into account while creating new edges. The proposed approach enables automatic generation of graphs corresponding to new layout designs with geometrical properties specified by graph attributes. It is illustrated by examples of apartment floor layouts generated by a prototype application implemented in Python.
•An attributed CP-graph as a model of the object being designed.•Innovative graph rules with embedding controlled by attribute values.•Generative graph grammar which considers both syntax and semantics.•A prototype application for generating building floor layouts.
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.
ABSTRACT
Researchers have proposed many approaches to generate floor plans using shape grammars. None of them, however, testifies the semantic relations among rooms. This paper presents a generic ...approach for grammar specification, grammar induction, validation, and design generation of house floor plans using their path graphs based on the reserved graph grammar (RGG) formalism. In our approach, the connectivity of a floor plan is analyzed by user-specified graph grammar transformation rules, also known as productions. Floor plans of houses in different styles share common attributes while retaining specific features. By identifying these features, our approach validates floor plans in different styles with user-specified graph productions. A graph grammar induction engine is also introduced to assist designers by automatically inferring graph productions from an input graph set. In addition, the derivation process in RGG offers the capability of generating floor plan designs. Two types of constraints, specified as attribute-sets, are introduced to generate floor plans meeting a wide range of requirements. To evaluate this generic approach, we design a set of productions to validate and generate floor plans in the style of Frank Lloyd Wright’s prairie houses. The results are discussed, and further research is suggested.
We present a method for automatically generating polygonal shapes from an example using a graph grammar. Most procedural modeling techniques use grammars with manually created rules, but our method ...can create them automatically from an example. Our graph grammars generate graphs that are locally similar to a given example. We disassemble the input into small pieces called primitives and then reassemble the primitives into new graphs. We organize all possible locally similar graphs into a hierarchy and find matching graphs within the hierarchy. These matches are used to create a graph grammar that can construct every locally similar graph. Our method generates graphs using the grammar and then converts them into a planar graph drawing to produce the final shape.
Bottom-Up/Top-Down Image Parsing with Attribute Grammar Han, Feng; Zhu, Song-Chun
IEEE transactions on pattern analysis and machine intelligence,
2009-Jan., 2009, 2009-Jan, 2009-1-00, 20090101, Letnik:
31, Številka:
1
Journal Article
Recenzirano
Odprti dostop
This paper presents a simple attribute graph grammar as a generative representation for made-made scenes, such as buildings, hallways, kitchens, and living rooms, and studies an effective ...top-down/bottom-up inference algorithm for parsing images in the process of maximizing a Bayesian posterior probability or equivalently minimizing a description length (MDL). Given an input image, the inference algorithm computes (or constructs) a parse graph, which includes a parse tree for the hierarchical decomposition and a number of spatial constraints. In the inference algorithm, the bottom-up step detects an excessive number of rectangles as weighted candidates, which are sorted in certain order and activate top-down predictions of occluded or missing components through the grammar rules. In the experiment, we show that the grammar and top-down inference can largely improve the performance of bottom-up detection.
This paper presents a framework for the automatic generation of floor plans based on adjacency relations among rooms. The adjacency can be generated from user-specified design requirements using a ...graph grammar formalism. We propose a set of grammar rules to generate graphs that represent adjacency relationships. Our solution overcomes the limitation of previous approaches that generate only rectangular floor plans. We define a set of constraints, such as plan size, room orientation and aspect ratio, for specifying the desired floor plans; and present a set of algorithms for placing rectangular or non-rectangular rooms and for generating non-rectangular floor plan boundaries. We demonstrate that our method can generate varied floor plans from user-specified design requirements.
•A formal mechanism for specifying high-level constraints for generating floor plans is presented.•A generic approach for generating floor plans from user-specified requirements as a graph data structure is described.•Algorithms for placing rectangular and non-rectangular rooms based on graph specified adjacencies are introduced.
The building sector consumes more than 70% of the electricity produced in the U.S., with Heating Ventilation and Air Conditioning (HVAC) systems accounting for half of the electricity consumption. ...Leaks in HVAC systems have a significant impact on the energy efficiency of buildings, resulting in up to 33% of energy loss. However, the current manual approach to inspection is time-consuming and reactive, leaving room for automation. This paper presents a framework to automatically evolve robot morphology without requiring human intervention to suite any given HVAC and ceiling design. Robot morphologies are optimized using graph heuristic search based on tasks and environment designs, followed by testing of navigation abilities of the best-evolved robot in diverse ceiling environments using reinforcement learning. Tests conducted in robot simulation tools, utilizing realistic HVAC designs retrieved from Building Information Models (BIMs), demonstrate that effortless navigation in complex ceiling environments can be achieved by the evolved robots.
•Proposed robot grammars for automated evolution of robot morphologies.•Created a graph neural network based heuristic search to predict robot performance.•Evaluated different robot morphologies using model predictive control.•Developed ceiling environments in a physics engine to train robot control agents.•Tested robot performance in realistic environments using reinforcement learning.
In this paper, we propose parallel graph-grammar-based algorithm for the longest-edge refinements and the pollution simulations in Lesser Poland area. We introduce graph-grammar productions for ...Rivara’s longest-edged algorithm for the local refinement of unstructured triangular meshes. We utilize the hyper-graph to represent the computational mesh and the graph-grammar productions to express the longest-edge mesh refinement algorithm. The parallelism in the original Rivara’s longest edge refinement algorithm is obtained by processing different longest edge refinement paths in different three ads. Our graph-grammar-based algorithm allows for additional parallelization within a single longest-edge refinement path. The graph-grammar-based algorithm automatically guarantees the validity and conformity of the generated mesh; it prevents the generation of duplicated nodes and edges, elongated elements with Jacobians converging to zero, and removes all the hanging nodes automatically from the mesh. We test the algorithm on generating a surface mesh based on a topographic data of Lesser Poland area. The graph-grammar productions also generate the layers of prismatic three-dimensional elements on top of the triangular mesh, and they break each prismatic element into three tetrahedral elements. Next, we propose graph-grammar productions generating element matrices and right-hand-side vectors for each tetrahedral element. We utilize the Streamline Upwind Petrov–Galerkin (SUPG) stabilization for the pollution propagation simulations in Lesser Poland area. We use the advection–diffusion-reaction model, the Crank–Nicolson time integration scheme, and the graph-grammar-based interface to the GMRES solver.
PDF
