Meta-modelling and graph grammars for multi-paradigm modelling in AToM<Superscript>3</Superscript>

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: edit, simulate, transform into another formalism, optimize and generate code. We store all (meta-)models as graphs, and thus, express model manipulations as graph grammars.We present the design and implementation of these concepts in AToM³ (A_To_ol for M_ulti-formalism, M_eta-M_odelling). AToM³ supports modelling of complex systems using different formalisms, all meta-modelled in their own right. Models in different formalisms may be transformed into a single common formalism for further processing. These transformations are specified by graph grammars. Mosterman and Vangheluwe [18] introduced the term multi-paradigm modelling to denote the combination of multiple formalisms, multiple abstraction levels, and meta-modelling. As an example of multi-paradigm modelling we present a meta-model for the Object-Oriented Continuous Simulation Language OOCSMP, in which we combine ideas from UML class diagrams (to express the OOCSMP model structure), Causal Block Diagrams (CBDs), and Statecharts (to specify the methods of the OOCSMP classes). A graph grammar is able to generate OOCSMP code, and then a compiler for this language (C-OOL) generates Java applets for the simulation execution.     

Event-driven grammars: relating abstract and concrete levels of visual languages

In this work we introduce event-driven grammars, a kind of graph grammars that are especially suited for visual modelling environments generated by meta-modelling. Rules in these grammars may be triggered by user actions (such as creating, editing or connecting elements) and in their turn may trigger other user-interface events. Their combination with triple graph transformation systems allows constructing and checking the consistency of the abstract syntax graph while the user is building the concrete syntax model, as well as managing the layout of the concrete syntax representation. As an example of these concepts, we show the definition of a modelling environment for UML sequence diagrams. A discussion is also presented of methodological aspects for the generation of environments for visual languages with multiple views, its connection with triple graph grammars, the formalization of the latter in the double pushout approach and its extension with an inheritance concept. This is a revised and extended version of a paper presented at the ICGT’04 conference, see [21].     

Combining unit and specification-based testing for meta-model validation and verification

Meta-models play a cornerstone role in Model-Driven Engineering as they are used to define the abstract syntax of modelling languages, and so models and all sorts of model transformations depend on them. However, there are scarce tools and methods supporting their Validation and Verification (V&V), which are essential activities for the proper engineering of meta-models.In order to fill this gap, we propose two complementary meta-model V&V languages. The first one has similar philosophy to the xUnit framework, as it enables the definition of meta-model unit test suites comprising model fragments and assertions on their (in-)correctness. The second one is directed to express and verify expected properties of a meta-model, including domain and design properties, quality criteria and platform-specific requirements.As a proof of concept, we have developed tooling for both languages in the Eclipse platform, and illustrate its use within an example-driven approach for meta-model construction. The expressiveness of our languages is demonstrated by their application to build a library of meta-model quality issues, which has been evaluated over the ATL zoo of meta-models and some OMG specifications. The results show that integrated support for meta-model V&V (as the one we propose here) is urgently needed in meta-modelling environments.     

General meta-model based co-simulations applied to mechanical systems

A fully functional meta-model co-simulation environment that supports integration of many different simulation tool specific models into a co-simulation is described in this paper.The continuously increasing performance of modern computer systems has a large influence on simulation technologies. It results in more and more detailed simulation models. Different simulation models typically focus on different parts (sub-systems) of the complete system, e.g., the gearbox of a car, the driveline, or even a single bearing inside the gearbox. To fully understand the complete system it is necessary to investigate several or all parts simultaneously. This is especially true for transient (dynamic) simulation models with several interconnected parts. One solution for a more complete and accurate system analysis is to couple different simulation models into one coherent simulation, also called a co-simulation. This also allows existing simulation models to be reused and preserves the investment in these models.Existing co-simulation applications are often capable of interconnecting two specific simulators where a unique interface between these tools is defined. However, a more general solution is needed to make co-simulation modelling applicable for a wider range of tools. Any such solution must also be numerically stable and easy to use in order to be functional for a larger group of people.The presented approach for mechanical system co-simulations is based upon a general framework for co-simulation and meta-modelling [9]. Several tool specific simulation models can be integrated and connected by means of a meta-model. A platform independent, centralised, meta-model simulator is presented that executes and monitors the co-simulation. All simulation tools that participate in the co-simulation implement a single, well defined, external interface that is based on a numerically stable method for force/moment interaction.     

上下文相关图文法的表达能力分析

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

Visual specification of measurements and redesigns for domain specific visual languages

Ensuring model quality is a key success factor in many computer science areas, and becomes crucial in recent software engineering paradigms like the one proposed by model-driven software development. Tool support for measurements and redesigns becomes essential to help developers improve the quality of their models. However, developing such helper tools for the wide variety of (frequently domain specific) visual notations used by software engineers is a hard and repetitive task that does not take advantage from previous developments, thus being frequently forgotten.In this paper we present our approach for the visual specification of measurements and redesigns for Domain Specific Visual Languages (DSVLs). With this purpose, we introduce a novel DSVL called SLAMMER that contains generalisations of some of the more used types of internal product measurements and redesigns. The goal is to facilitate the task of defining measurements and redesigns for any DSVL, as well as the generation of tools from such specification reducing or eliminating the necessity of coding. We rely on the use of visual patterns for the specification of the relevant elements for each measurement and redesign type. In addition, SLAMMER allows the specification of redesigns either procedurally or by means of graph transformation rules. These redesigns can be triggered when the measurements reach a certain threshold.These concepts have been implemented in the meta-modelling tool AToM³. In this way, when a DSVL is designed, it is possible to specify measurements and redesigns that will become available in the final modelling environment generated for the language. As an example, we show a case study in the web modelling domain.     

An institution theory of formal meta-modelling in graphically extended BNF

Meta-modelling plays an important role in model driven software development.In this paper,a graphic extension of BNF (GEBNF) is proposed to define the abstract syntax of graphic modelling languages.Fro...     

The equivalence of four extensions of context-free grammars

There is currently considerable interest among computational linguists in grammatical formalisms with highly restricted generative power. This paper concerns the relationship between the class of string languages generated by several such formalisms, namely, combinatory categorial grammars, head grammars, linear indexed grammars, and tree adjoining grammars. Each of these formalisms is known to generate a larger class of languages than context-free grammars. The four formalisms under consideration were developed independently and appear superficially to be quite different from one another. The result presented in this paper is that all four of the formalisms under consideration generate exactly the same class of string languages.This work has been supported by NSF Grants MCS-82-19116-CER, MCS-82-07294, DCR-84-10413, IRI-8909810, ARO Grant DAA29-84-9-0027, and DARPA Grant N0014-85-K0018.     

Parsing nonlinear languages

The diagrammatic approach to user interfaces for computer-aided software development toolkits, visual query systems, and visual programming environments, is based on the use of diagrams and charts traditionally drawn on paper. In particular, the VLG system (Visual Language Generator) has been proposed to generate icon-oriented visual languages customized for given applications. The syntactical model underlying the interpretation of a visual language in VLG has been designed to describe icon-oriented visual languages. In order to enable the VLG system to apply to any kind of graphical languages, like diagrammatic ones, it is necessary to find a more general syntactical model able to support both their generation and interpretation. This paper addresses the comprehension of the features that a grammatical formalism for nonlinear languages must have to match any requirement for an efficient parsing. To this aim, relation grammars support an easy implementation of a general parsing algorithm for multidimensional languages, parametric with respect to the rewriting rules of the grammar. We compare the expressive power of relation grammars to grammatical formalisms for graph grammars     

On the Geometric Modelling of Visual Languages

We present arguments for the complementary role that intrinsically geometric models of visual languages can play in many applications, alongside non-geometry based models (such those based on graph grammars, logical predicates or algebraic structures). We characterise which models are intrinsically geometric, and illustrate the concept by providing such a model for higraphs. Further, we examine the relevance of geometric models to the design and implementation of tools which effectively support users in working with visual languages.     

Spinal-Formed Context-Free Tree Grammars

In this paper we introduce a restricted model of context-free tree grammars called spine grammars, and study their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It is shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduce acceptors called linear pushdown tree automata, and show that linear pushdown tree automata accept exactly the class of tree languages generated by spine grammars. Linear pushdown tree automata are obtained from pushdown tree automata with a restriction on duplicability for the pushdown stacks. Received May 29, 1998, and in revised form April 27, 1999, and in final form May 10, 1999.     

Distributed Event Graphs: Formalizing Component-based Modelling and Simulation

In this work an extension to the classical Event Graphs formalism for discrete-event simulation is presented. The extensions are oriented towards the specification of component-based models. The abstract syntax has been defined through meta-modelling. Several methodological issues are discussed, concerning the use of two different meta-modelling levels or collapsing the language into a single one, where “instance-of” relationships are used between processes and their classes. The operational semantics have been defined through graph transformation. This formal definition enables analysis before code is generated from the model. The syntax and semantics of the visual language have been implemented in the multi-paradigm tool AToM³, together with a code generator that produces stand-alone applications able to run the analysed models in real-time.     

A grammatical approach to self-organizing robotic systems

In this paper, we define a class of graph grammars that can be used to model and direct concurrent robotic self-assembly and similar self-organizing processes. We give several detailed examples of the formalism and then focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). In both cases, we characterize the number of concurrent steps required to achieve the assembly. We also show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the self-assembly of robotic parts.     

TOTEM: Reconciling multi-level modelling with standard two-level modelling

Model driven Engineering (MDE) advocates the active use of models throughout the different software development phases. In MDE, models are described using meta-models, one meta-level above. This approach effectively leaves developers with one single meta-level to create their models. However, there are scenarios where the use of multiple meta-levels results in simpler models with less accidental complexity. Hence, to simplify modelling in these cases, several multi-level modelling approaches and tools have recently emerged to increase the flexibility in modelling. While they provide advanced primitives to simplify modelling, there are possibilities to improve interoperability with mainstream two-level modelling approaches based on the Meta-Object Facility (MOF) standard of the Object Management Group (OMG), and achieve wider adoption.For this purpose, we first characterise the design space of multi-level modelling approaches using a feature model. On such a basis, we provide a detailed comparison of existing multi-level modelling tools, identifying gaps and research opportunities. As a result of this gap analysis, we propose a new approach to multi-level modelling that embeds multiple meta-levels within one meta-model (i.e., encoding objects as classes, and instantiation as inheritance), and a tool – called TOTEM – which implements these concepts. The tool capabilities and its benefits in terms of interoperability with mainstream, standard modelling frameworks are illustrated through an example, as well as with empirical and analytical evaluations.     

From types to type requirements: genericity for model-driven engineering

Model-driven engineering (MDE) is a software engineering paradigm that proposes an active use of models during the development process. This paradigm is inherently type-centric, in the sense that models and their manipulation are defined over the types of specific meta-models. This fact hinders the reuse of existing MDE artefacts with other meta-models in new contexts, even if all these meta-models share common characteristics. To increase the reuse opportunities of MDE artefacts, we propose a paradigm shift from type-centric to requirement-centric specifications by bringing genericity into models, meta-models and model management operations. For this purpose, we introduce so-called concepts gathering structural and behavioural requirements for models and meta-models. In this way, model management operations are defined over concepts, enabling the application of the operations to any meta-model satisfying the requirements imposed by the concept. Model templates rely on concepts to define suitable interfaces, hence enabling the definition of reusable model components. Finally, similar to mixin layers, templates can be defined at the meta-model level as well, to define languages in a modular way, as well as layers of functionality to be plugged-in into other meta-models. These ideas have been implemented in MetaDepth, a multi-level meta-modelling tool that integrates action languages from the Epsilon family for model management and code generation.     

Interactive Iconized Grammar-Based Pailou Modelling

Pailous are representative Chinese architectural works used for commemoration. However, their geometric structure and semantic construction rules are too complex for quick and intuitive modelling using traditional modelling tools. We propose an intuitive modelling system for the stylized creation of pailous for novices. Our system encapsulates structural components as icons and semantic layouts as topological graphs, using which users create and manipulate icons with topological recommendations. The interpreter automatically and immediately transforms a graph to its corresponding model using built-in components with the proposed parametric L-system grammars derived from architectural rules. Using this system to re-create existing representative pailous and design imaginary ones yields results with the desired visual complexities. In comparison to Maya, a 3D modelling tool, when modelling a pailou and toukung, our system is effective and simple, and eliminates the need to remember and understand complex rules.     

图文法综述

形式语言理论对计算机科学的发展起了重大的作用,作为对传统字符文法扩展的图文法的形式化研究,其重要意义是不言而喻的.本文在概述图文法的产生、发展和现状的基础上,着重介绍了从一维字符文法扩展到二维图文法所出现的新问题,以及在形式化处理上引出的新方法,其中最主要的是嵌入问题的解决、文法类型的划分和成员问题的判定.文中以目前较为流行的图文法为例,特别是一些典型的上下文无关和上下文相关的图文法,对上述的问题进行了深入的讨论,指出了现有方法中的一些不足之处,并展望了图文法今后值得研究的问题和方向.     

UML元模型图实例自动生成算法

UML元模型建模与实例生成是软件自动生成技术的重要环节之一,相关理论和技术在领域建模语言DSL中得到广泛应用。元模型自动生成实例技术不仅可以降低软件开发难度和成本,还可以提高软件开发效率。在已有元模型实例生成图语法理论的基础上,提出相应的元模型图实例自动生成算法,证明了该算法与图语法的等价性。并且在可视化UML建模平台中实现了这一算法,得到了从UML元模型自动生成大量实例的预期结果。     

THE COMPUTATIONAL COMPLEXITY OF THE UNIVERSAL RECOGNITION PROBLEM FOR PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context-free grammars, multiple context-free grammars, and their subclasses are discussed.