The Singapore Government has embarked on a project to establish a three-dimensional city model and collaborative data platform for Singapore. The research herein contributes to this endeavour by ...developing a methodology and algorithms to automate the conversion of Building Information Models (BIM), in the Industry Foundation Classes (IFC) data format, into CityGML building models, capturing both geometric and semantic information as available in the BIM models, and including exterior as well as interior structures. We adopt a Triple Graph Grammar (TGG) to formally relate IFC and CityGML, both semantically and geometrically, and to transform a building information model, expressed as an IFC object graph, into a city model expressed as a CityGML object graph. The work pipeline includes extending the CityGML data model with an Application Domain Extension (ADE), which allows capturing information from IFC that is relevant in the geospatial context but at the same time not supported by CityGML in its standard form. In this paper, we elaborate on the triple graph grammar approach and the motivation and roadmap for the development of the ADE. While a fully complete and lossless conversion may never be achieved, this paper suggests that both a TGG and an ADE are natural choices for supporting the conversion between IFC and CityGML.
It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the ...non-uniform setting, in which the grammar is considered to be fixed rather than being part of the input. Little is known about restrictions under which truly uniform polynomial parsing is possible. In this paper we propose a low-degree polynomial-time algorithm that solves the uniform parsing problem for a restricted type of hyperedge-replacement grammars which we expect to be of interest for practical applications.
The paper introduces a definition of dual graph grammar. It enables two graphs to share information in a synchronized way. A smart city example application, which is an outdoor lighting control ...system utilizing the dual graph grammar, is also demonstrated. The system controls dimming of street lights which is based on traffic intensity. Each luminaire’s light level is adjusted individually to comply with the lighting norms to ensure safety. Benefits of applying the dual graph grammar are twofold. First, it increases expressive power of the mathematical model that the system uses. It becomes possible to take into account complex geographical distribution of sensors and logical dependencies among them. Second, it increases the system’s efficiency by reducing the problem size during run-time. Experimental results show a reduction of the computation time by a factor of 2.8. The approach has been verified in practice.
This article presents an analog integrated circuit automated topology synthesis framework, where circuit topology synthesis can be efficiently realized by encoding circuit topology generation process ...as tree structure construction. Then the tree structures are decoded into circuit topologies. Our proposed method can not only handle large circuit designs but also generate creative topologies. To ensure only unique circuit topologies to be generated, two levels of isomorphism checks are performed at both tree structure level and circuit topology level. Then the generated un-sized circuit topologies are efficiently evaluated through a new method, which integrates topological symbolic analysis with <inline-formula> <tex-math notation="LaTeX">g_{m} </tex-math></inline-formula>/<inline-formula> <tex-math notation="LaTeX">I_{D} </tex-math></inline-formula> methodology and curve-fitting technique. Along with the small-signal analysis, both linear and nonlinear programming techniques are utilized for topology feasibility checking. With only a small number of circuit topologies through the fast evaluation stage toward the subsequent detailed sizing and further evaluation, the efficiency of the whole circuit synthesis process can be significantly improved. The experimental results demonstrate high efficiency, strong reliability, and wide applicability of our proposed methods.
In engineering and architecture, different approaches have been developed that share the use of graph transformation to automate design processes or to search for design solutions by means of ...computational design synthesis. In order to give an overview of these approaches, we provide a review of articles published in the last decade. Forty-eight articles were reviewed to determine similarities and differences of these approaches. Research fields in method development for the representation of design problems and the processing of graph transformations, as well as the application of graph transformations in engineering, architecture, and shape grammars were identified. Different approaches for the documentation of the vocabulary and the rules were examined. Finally, different approaches for rule applications were analyzed. Based on found limitations, future research directions are suggested.
Hypergraph Lambek grammars Pshenitsyn, Tikhon
Journal of logical and algebraic methods in programming,
November 2022, 2022-11-00, Letnik:
129
Journal Article
Recenzirano
In the graph grammar theory, there is a natural generalization of the context-free grammar approach to graphs called hyperedge replacement grammar (HRG). The latter is based on the hyperedge ...replacement procedure, and it preserves the main principles and properties of context-free grammars (e.g. the pumping lemma). In the string case, there is an alternative approach to describing formal languages, which was introduced by J. Lambek; it is based on a substructural logic called the Lambek calculus. In this paper, we generalize this calculus and this grammar approach to hypergraphs, which results in defining the hypergraph Lambek calculus (HL) and hypergraph Lambek grammars (HL-grammars). We show how to embed the Lambek calculus in HL justifying that the presented generalization is appropriate. After that, we study several structural properties of HL and turn to the question of expressive power of its grammars. It appears that HL-grammars are more powerful than HRGs while having the same algorithmic complexity with them; in particular, we show that intersection of a language generated by an HRG and of a language generated by an HL-grammar can be generated by some HL-grammar as well. Consequently, HL-grammars might be considered as enhancement of HRGs.
Massively applied in critical systems, formal methods of specification and verification have gained importance in a world where computer systems grow larger and larger. There are long-known ...challenges to teaching formal methods in higher education. But, as it is often considered an advanced topic of software engineering, it is rarely cogitated in basic education. Aiming at this unusual public, this paper explores a new take on formal specification: the development of fundamental modeling and evaluation skills, rather than the technical competence to prove correctness. Known challenges and strategies are revisited highlighting what changes when the teaching moves from universities to schools. Studies approaching related topics with kids and teens are discussed. Then game design with Graph Grammars is presented as an example of how to tackle the mentioned challenges and employ the respective strategies.
We revisit graph grammar and graph parsing as tools for recognizing graphics. A top-down approach for parsing families of handwritten graphics containing different kinds of symbols and of structural ...relations is proposed. It has been tested on two distinct domains, namely the recognition of handwritten mathematical expressions and of handwritten flowcharts. In the proposed approach, a graphic is considered as a labeled graph generated by a graph grammar. The recognition problem is translated into a graph parsing problem: Given a set of strokes (input data), a parse tree which represents the best interpretation is extracted. The graph parsing algorithm generates multiple interpretations (consistent with the grammar) that can be ranked according to a global cost function that takes into account the likelihood of symbols and structures. The parsing algorithm consists in recursively partitioning the stroke set according to rules defined in the graph grammar. To constrain the number of partitions to be evaluated, we propose the use of a hypothesis graph, built from data-driven machine learning techniques, to encode the most likely symbol and relation hypotheses. Within this approach, it is easy to relax the stroke ordering constraint allowing interspersed symbols, as opposed to some previous works. Experiments show that our method obtains accuracy comparable to methods specifically developed to recognize domain-dependent data.
PDF
