Model management is a central activity in Software Engineering. The most challenging aspect of model management is to keep inter-related models consistent with each other while they evolve. As a ...consequence, there is a lot of scientific activity in this area, which has produced an extensive body of knowledge, methods, results and tools. The majority of these approaches, however, are limited to binary inter-model relations; i.e. the synchronisation of exactly two models. Yet, not every multi-ary relation can be factored into a family of binary relations. In this paper, we propose and investigate a novel
comprehensive system
construction, which is able to represent multi-ary relations among multiple models in an
integrated
manner and thus serves as a
formal foundation
for artefacts used in consistency management activities involving multiple models. The construction is based on the definition of
partial
commonalities among a set of models using the same language, which is used to denote the (local) models. The main
theoretical
results of this paper are proofs of the facts that comprehensive systems are an admissible environment for (i) applying formal means of consistency verification (diagrammatic predicate framework), (ii) performing algebraic graph transformation (weak adhesive HLR category), and (iii) that they generalise the underlying setting of graph diagrams and triple graph grammars.
Context-sensitive graph grammars have been intuitive and rigorous formalisms for specifying visual programming languages, as they are sufficient expressive and equipped with parsing mechanisms. ...Parsing has been a fundamental issue in the research of context-sensitive graph grammars. However, the existent parsing algorithms are either inefficient or confined to a minority of graph grammars. This paper proposes a general parsing algorithm with two embedded strategies, context matching and production-set partitioning. The two strategies can greatly narrow down the search space of redexes and thus significantly improve parsing efficiency, even though the worst-case time complexity is not theoretically reduced. Moreover, a detailed case study and an experiment are provided accordingly to demonstrate the paring process and performance of the proposed algorithm.
We explain the foundations of a new class of formal languages for the construction of large Feynman diagrams which contribute to solutions of all combinatorial Dyson–Schwinger equations in a given ...strongly coupled gauge field theory. Then we build a new Hopf algebraic structure on non-perturbative production rules which leads us to formulate the halting problem for the corresponding replacing–gluing graph grammars in our formal graph languages on the basis of Manin’s renormalization Hopf algebra. In addition, we apply topology of graphons to associate a complexity parameter to this new class of graph grammars. At the final step, we address some applications of our new formal language platform to Quantum Field Theory. The first application concerns the constructive role of non-perturbative graph languages in dealing with quantum gauge symmetries in the context of the Hopf ideals generated by Slavnov–Taylor or Ward–Takahashi identities. The second application concerns the importance of the complexities of non-perturbative replacing–gluing graph grammars in formulating a new generalization of the circuit complexity on the space of Dyson–Schwinger equations. We provide a geometric interpretation of non-perturbative circuit complexities. The third application concerns the impact of non-perturbative replacing–gluing graph grammars in providing some new tools for the computation of the Kolmogorov complexity of Dyson–Schwinger equations.
In the field of Model-Driven Engineering, Triple Graph Grammars (TGGs) play an important role as a rule-based means of implementing consistency management. From a declarative specification of a ...consistency relation, several operations including forward and backward transformations, (concurrent) synchronisation, and consistency checks can be automatically derived. For TGGs to be applicable in realistic application scenarios, expressiveness in terms of supported language features is very important. A TGG tool is schema compliant if it can take domain constraints, such as multiplicity constraints in a meta-model, into account when performing consistency management tasks. To guarantee schema compliance, most TGG tools allow application conditions to be attached as necessary to relevant rules. This strategy is problematic for at least two reasons: First, ensuring compliance to a sufficiently expressive schema for all previously mentioned derived operations is still an open challenge; to the best of our knowledge, all existing TGG tools only support a very restricted subset of application conditions. Second, it is conceptually demanding for the user to indirectly specify domain constraints as application conditions, especially because this has to be completely revisited every time the TGG or domain constraint is changed. While domain constraints can in theory be automatically transformed to obtain the required set of application conditions, this has only been successfully transferred to TGGs for a very limited subset of domain constraints. To address these limitations, this paper proposes a search-based strategy for achieving schema compliance. We show that all correctness and completeness properties, previously proven in a setting without domain constraints, still hold when schema compliance is to be additionally guaranteed. An implementation and experimental evaluation are provided to support our claim of practical applicability.
In this paper, we introduce a new approach based on properties of graph grammars to detect conflicts of interest (COIs) in a field represented in the form of a social network. The approach consists ...of specializing the adaptive star graph grammar (ASGG) of Drewes et al. (Theor Comput Sci 411:3090–3109, 2010) to express kind of subgraphs that we call
K
4
-type tournament graphs, corresponding to COIs, that cannot be generated by the node replacement graph grammar. This approach, called graph grammar and
K
4
-type tournament-based approach to detect conflicts of interest
(
G
G
K
4
T
-
C
O
I
s
)
, is applied to detect COIs in the review process of papers accepted in an international conference which is represented through a social network. In this contribution, the principle of the used graph grammar is not to consider all the generated language but only subgraphs with some properties (corresponding to special graph queries), which identify parts of the social network representing COIs. For evaluating the performances and the efficiency of our proposition, experimentations have been done by comparing it with concurrent methods in the literature. The obtained results have shown that the approach GG
K
4
T-COIs performs better than the investigated state-of-the-art approaches in terms of type and number of detected COIs.
Taxonomies play a central role in conceptual domain modeling, having a direct impact in areas such as knowledge representation, ontology engineering, and software engineering, as well as knowledge ...organization in information sciences. Despite this, there is little guidance on how to build high-quality taxonomies, with notable exceptions being the OntoClean methodology, and the ontology-driven conceptual modeling language OntoUML. These techniques take into account the ontological meta-properties of types to establish well-founded rules on the formation of taxonomic structures. In this paper, we show how to leverage the formal rules underlying these techniques in order to build taxonomies which are correct by construction. We define a set of correctness-preserving operations to systematically introduce types and subtyping relations into taxonomic structures. In addition to considering the ontological micro-theory of endurant types underlying OntoClean and OntoUML, we also employ the MLT (Multi-Level Theory) micro-theory of high-order types, which allows us to address multi-level taxonomies based on the powertype pattern. To validate our proposal, we formalize the model building operations as a graph grammar that incorporates both micro-theories. We apply automatic verification techniques over the grammar language to show that the graph grammar is sound, i.e., that all taxonomies produced by the grammar rules are correct, at least up to a certain size. We also show that the rules can generate all correct taxonomies up to a certain size (a completeness result).
Dynamical graph grammars (DGGs) are capable of modeling and simulating the dynamics of the cortical microtubule array (CMA) in plant cells by using an exact simulation algorithm derived from a master ...equation; however, the exact method is slow for large systems. We present preliminary work on an approximate simulation algorithm that is compatible with the DGG formalism. The approximate simulation algorithm uses a spatial decomposition of the domain at the level of the system's time-evolution operator, to gain efficiency at the cost of some reactions firing out of order, which may introduce errors. The decomposition is more coarsely partitioned by effective dimension (
= 0 to 2 or 0 to 3), to promote exact parallelism between different subdomains within a dimension, where most computing will happen, and to confine errors to the interactions between adjacent subdomains of different effective dimensions. To demonstrate these principles we implement a prototype simulator, and run three simple experiments using a DGG for testing the viability of simulating the CMA. We find evidence indicating the initial formulation of the approximate algorithm is substantially faster than the exact algorithm, and one experiment leads to network formation in the long-time behavior, whereas another leads to a long-time behavior of local alignment.
•We propose a new context-sensitive graph grammar formalism called E-EGG in short.•E-EGG introduces new mechanisms to tackle bidirectional transformation between BPMN and BPEL.•Steps to achieve ...transformation and check correctness of BPMN structure are presented.•Corresponding algorithms are further designed and analyzed.•A case study on transformation from BPMN to BPEL is discussed.
A graph grammar is a formal tool for providing rigorous but intuitive ways to define visual languages. Based on an existing graph grammar, this paper proposes new context-sensitive graph grammar formalism called the Extension of Edge-based Graph Grammar, or E-EGG. The E-EGG introduces new mechanisms into grammatical specifications, productions, operations and so on in order to conveniently treat the bidirectional transformation between the Business Process Modeling Notation (BPMN) and the Business Process Execution Language (BPEL). Besides formal definitions of the E-EGG are provided, steps and algorithms to achieve the bidirectional transformation and to check the correctness of BPMN models’ structure are presented. Finally, a case study on transformation from BPMN models to BPEL codes is provided to show how the parsing algorithm of the E-EGG works.
Visual Programming Languages have been widely adopted in design and comprehension of sophisticated systems. Context-sensitive graph grammar formalisms are suitable tools for specifying these ...languages, since they are intuitive and possess sufficient expressive power and usability. Nevertheless, some of the formalisms whose contexts are implicitly or incompletely represented in productions, called implicit context-sensitive graph grammars, suffer inherent weakness in intuitiveness and limitations in parsing algorithms. To address these issues, this paper formally presents a notion of context on the underlying concepts of partial and total precedence relations, characterizes their fundamental properties, and establishes a connection between contexts and their instances (also called context graphs elsewhere), based on the Reserved Graph Grammar formalism, a representative of implicit graph grammars. Moreover, three typical applications of contexts are illustrated, which show that contexts can both facilitate the comprehension and design of implicit graph grammars so as to enhance their intuitiveness, and make the existent efficient parsing algorithms more widely applicable.
This book constitutes the refereed proceedings of the Third International Conference on Graph Transformations, ICGT 2006. The book presents 28 revised full papers together with 3 invited lectures. ...All current aspects in graph drawing are addressed including graph theory and graph algorithms, theoretic and semantic aspects, modeling, tool issues and more. Also includes accounts of a tutorial on foundations and applications of graph transformations, and of ICGT Conference satellite events.
