Search

Pervasive Healthcare systems are breeding rapidly and distributed systems such as fog, cloud, and IoT have made it possible for these systems to scale extensively with a certain need to sustain interoperability, reliability, availability, and response time. Notwithstanding those remarkable efforts that have been conducted for the architecting of such systems, there is a certain obligation toward the design of an architecture for the domain to constitute the aforementioned requirements. Our goal in this paper is to present a software architecture for IoT-based healthcare systems to address the above-mentioned non-functional requirements that include best practices of IoT, Fog, and Cloud planes. The proposed architecture is illustrated with 4 + 1 views and graph transformation is used to transform the models and expressing operational semantics. The architecture tradeoff analysis method is applied to evaluate different scenarios and both formal verifications and trade-off analysis proved the eligibility and competence of the proposed architecture.

The ability to assess the reliability of safety-critical systems is one of the most crucial requirements in the design of modern safety-critical systems where even a minor failure can result in loss of life or irreparable damage to the environment. Model checking is an automatic technique that verifies or refutes system properties by exploring all reachable states (state space) of a model. In large and complex systems, it is probable that the state space explosion problem occurs. In exploring the state space of systems modeled by graph transformations, the rule applied on the current state specifies the rule that can perform on the next state. In other words, the allowed rule on the current state depends only on the applied rule on the previous state, not the ones on earlier states. This fact motivates us to use a Markov chain (MC) to capture this type of dependencies and applies the Estimation of Distribution Algorithm (EDA) to improve the quality of the MC. EDA is an evolutionary algorithm directing the search for the optimal solution by learning and sampling probabilistic models through the best individuals of a population at each generation. To show the effectiveness of the proposed approach, we implement it in GROOVE, an open source toolset for designing and model checking graph transformation systems. Experimental results confirm that the proposed approach has a high speed and accuracy in comparison with the existing meta-heuristic and evolutionary techniques in safety analysis of systems specified formally through graph transformations.

Electrocardiography (ECG) signal recognition is one of the popular research topics for machine learning. In this paper, a novel transformation called tower graph transformation is proposed to classify ECG signals with high accuracy rates. It employs a tower graph, which uses minimum, maximum and average pooling methods altogether to generate novel signals for the feature extraction. In order to extract meaningful features, we presented a novel one-dimensional hexadecimal pattern. To select distinctive and informative features, an iterative ReliefF and Neighborhood Component Analysis (NCA) based feature selection is utilized. By using these methods, a novel ECG signal classification approach is presented. In the preprocessing phase, tower graph-based pooling transformation is applied to each signal. The proposed one-dimensional hexadecimal adaptive pattern extracts 1536 features from each node of the tower graph. The extracted features are fused and 15,360 features are obtained and the most discriminative 142 features are selected by the ReliefF and iterative NCA (RFINCA) feature selection approach. These selected features are used as an input to the artificial neural network and deep neural network and 95.70% and 97.10% classification accuracy was obtained respectively. These results demonstrated the success of the proposed tower graph-based method.

Embedded real-time systems generate state sequences where time elapses between state changes. Ensuring that such systems adhere to a provided specification of admissible or desired behavior is essential. Formal model-based testing is often a suitable cost-effective approach. We introduce an extended version of the formalism of symbolic graphs, which encompasses types as well as attributes, for representing states of dynamic systems. Relying on this extension of symbolic graphs, we present a novel formalism of timed graph transformation systems (TGTSs) that supports the model-based development of dynamic real-time systems at an abstract level where possible state changes and delays are specified by graph transformation rules. We then introduce an extended form of the metric temporal graph logic (MTGL) with increased expressiveness to improve the applicability of MTGL for the specification of timed graph sequences generated by a TGTS. Based on the metric temporal operators of MTGL and its built-in graph binding mechanics, we express properties on the structure and attributes of graphs as well as on the occurrence of graphs over time that are related by their inner structure. We provide formal support for checking whether a single generated timed graph sequence adheres to a provided MTGL specification. Relying on this logical foundation, we develop a testing framework for TGTSs that are specified using MTGL. Lastly, we apply this testing framework to a running example by using our prototypical implementation in the tool AutoGraph.

International audience; In this paper, we consider two of the currently popular semantic frameworks: Abstract Meaning Representation (AMR)a more abstract framework, and Universal Conceptual Cognitive Annotation (UCCA)-an anchored framework. We use a corpus-based approach to build two graph rewriting systems, a deterministic and a non-deterministic one, from the former to the latter framework. We present their evaluation and a number of ambiguities that we discovered while building our rules. Finally, we provide a discussion and some future work directions in relation to comparing semantic frameworks of different flavors.

Generalized from image and language translation, the goal of graph translation or transformation is to generate a graph of the target domain on the condition of an input graph of the source domain. Existing works are limited to either merely generating the node attributes of graphs with fixed topology or only generating the graph topology without allowing the node attributes to change. They are prevented from simultaneously generating both node and edge attributes due to: (1) difficulty in modeling the iterative, interactive, and asynchronous process of both node and edge translation and (2) difficulty in learning and preserving the inherent consistency between the nodes and edges in generated graphs. A general, end-to-end framework for jointly generating node and edge attributes is needed for real-world problems. In this paper, this generic problem of multi-attributed graph translation is named and a novel framework coherently accommodating both node and edge translations is proposed. The proposed generic edge translation path is also proven to be a generalization of existing topology translation models. Then, in order to discover and preserve the consistency of the generated nodes and edges, a spectral graph regularization based on our nonparametric graph Laplacian is designed. In addition, two extensions of the proposed model are developed for signed and directed graph translation. Lastly, comprehensive experiments on both synthetic and real-world practical datasets demonstrate the power and efficiency of the proposed method.

Paul Erdos said about the 3x + 1 problem, “Mathematics is not yet ready for such problems”. And he is seemingly right. Although we cannot solve this problem either, we provide some results about its structure. The so-called Collatz graph is iteratively transformed into a sequence of graphs by making use of some hidden structure information. It turns out that the transformation of graphs corresponds to a sequence of sets of numbers. It is shown that if the union of these number sets were equal to the set of integers greater than one, the famous Collatz conjecture would be true. OA platinum

Safety is one of the most important features of modern software systems, especially safety-critical systems such as nuclear power plants, which can be checked exactly by model checking. Model checking is a formal verification technique that analyzes system properties through exploring all reachable states (state space) of a model of a system. The problem of the technique is that it confronts the state space explosion in large and complex systems due to exponential memory usage. Recent researches show that a partial and intelligent exploration of the state space can be a suitable solution to overcome this problem. In this paper, we propose a two-phase model checking for safety analysis of systems specified formally through graph transformations. In the first phase, the beam-search algorithm explores the state space to a specific number of states. In case of failure of the phase, the second phase starts: in systems specified through graph transformations, the rule applied on the previous state can determine the rule that can perform on the next state. In other words, the rule on current state depends on only the rule applied to previous state, not the one on earlier states. Hence, a Markov chain (MC) is estimated to capture dependencies between the sequence of applied rules in the state space explored by the beam-search algorithm. The MC is then employed to explore the remainder of the state space intelligently. To evaluate the effectiveness of the two-phase model checking, we implement it in GROOVE, an open source toolset for designing and model checking graph transformation systems. Experimental results show that the two-phase model checking has the high speed and accuracy in comparison with the existing meta-heuristic and evolutionary techniques.

Network morphism is an effective learning scheme to morph a well-trained neural network to a new one with the network function completely preserved. However, existing network morphism scheme addresses only basic morphing types on the layer level. In this research, we address the central problem of network morphism at a higher level, i.e., how a convolutional layer can be morphed into an arbitrary module of a neural network. To simplify the representation of a network, we abstract a module as a graph with blobs as vertices and convolutional layers as edges. Based on this graph, the morphing process can be formulated as a graph transformation problem. Two atomic morphing operations are introduced to construct the graphs, based on which modules are classified into two families, i.e., simple morphable modules and complex modules. We present practical morphing solutions for both families, and prove that any module can be morphed from a single convolutional layer. Extensive experiments have been conducted based on the state-of-the-art ResNet on benchmarks to verify the effectiveness of the proposed solution.

Conversion of Industry Foundation Classes (IFC) building models into CityGML city models is one of the operational scenarios for BIM–GIS integration, with a variety of applications producing and consuming data on either side. Given the in‐depth cross‐domain knowledge required to specify such conversions, the heterogeneity of the IFC input data and the use cases for the resulting CityGML, flexible and configurable solutions are needed that make conversion details accessible to domain specialists. Graph transformation as a conversion method fulfils these requirements. We propose to extend the modularity given by single transformation rules at a more coarse‐grained level and identify four layers with modules of associated rules. We describe a self‐contained set of rules across these modules and demonstrate its application to a range of building models., Virtual Singapore

Graph transformation theory relies upon the composition of rules to express the effects of sequences of rules. In practice, graphs are often subject to constraints, ruling out many candidates for composed rules. Focusing on the case of sesqui-pushout (SqPO) semantics, we develop a number of alternative strategies for computing compositions, each theoretically and with an implementation via the Python API of the Z3 theorem prover. The strategies comprise a straightforward generate-and-test strategy based on forbidden graph patterns, a variant with a more implicit logical encoding of the negative constraints, and a modular strategy, where the patterns are decomposed as forbidden relation patterns. For a toy model of polymer formation in organic chemistry, we compare the performance of the three strategies in terms of execution times and memory consumption., Comment: In Proceedings GCM 2020, arXiv:2012.01181

Due to the development needs of the intelligent manufacturing industry, the use of drones is expanding indefinitely, and at the same time, extremely high requirements are imposed on the autonomous navigation of drones to reduce human intervention. This paper presents an UAV/ UGV scheduling problem in which the UAV needs to be recharged by the UGV in order to working in persistent tasks, and meanwhile, the UGV need to visits UGV working depots. Two different problem are presented: fixed charging sets problem (FCSP) and discrete charging sets problem (DCSP). In FCSP, charging sets are fixed, and a two-stage travelling salesman problem method is proposed to solve the problem. DCSP is a modification of FCSP while charging segments are discrete into serval segments, an graph transformation approach was proposed to transform DCSP into GTSP, so DCSP can be resolved by using GTSP solvers. Simulation results shows that both DCSP and FCSP can ensure UAV/UGV work in persistent tasks, and the graph transformation algorithm can efficiently transform DCSP into GTSP.

Polyhedral auto-transformation frameworks are known to find efficient loop transformations that maximize locality and parallelism and minimize synchronization. While complex loop transformations are routinely modeled in these frameworks, they tend to rely on ad hoc heuristics for loop fusion. Although there exist multiple loop fusion models with cost functions to maximize locality and parallelism, these models involve separate optimization steps rather than seamlessly integrating with other loop transformations like loop permutation, scaling, and shifting. Incorporating parallelism-preserving loop fusion heuristics into existing affine transformation frameworks like Pluto, LLVM-Polly, PPCG, and PoCC requires solving a large number of Integer Linear Programming formulations, which increase auto-transformation times significantly. In this work, we incorporate polynomial time loop fusion heuristics into the Pluto-lp-dfp framework. We present a data structure called the fusion conflict graph (FCG), which enables us to efficiently model loop fusion in the presence of other affine loop transformations. We propose a clustering heuristic to group the vertices of the FCG, which further enables us to provide three different polynomial time greedy fusion heuristics, namely, maximal fusion , typed fusion , and hybrid fusion , while maintaining the compile time improvements of Pluto-lp-dfp over Pluto. Our experiments reveal that the hybrid fusion model, in conjunction with Pluto’s cost function, finds efficient transformations that outperform PoCC and Pluto by mean factors of 1.8× and 1.07×, respectively, with a maximum performance improvement of 14× over PoCC and 2.6× over Pluto.

Much work has been carried out on the topic of BIM-GIS integration. As a technical challenge in particular, research and development tackle the standard data formats of the two areas and aim for the conversion between, linking of or overarching querying over data sources of these formats. Usually, these operational cases (conversion, linking, querying) are examined in isolation or even treated as mutually exclusive and competing approaches. With Triple Graph Grammars, we propose to apply a method that allows to derive solutions for these operational cases from a common generic ruleset. We demonstrate this approach in a proof-of-concept implementation using eMoflon. Our work focusses on IFC and CityGML and we present and discuss a first end-to-end demonstration of integrating these standards with the proposed method. Going forward such representation of the correlation between IFC and CityGML, declarative, independent of particular operational implementations, can serve as a vehicle to capture and document acknowledged integration schemes for IFC and CityGML, complementing these two standards with a specification of their correlation.

As a crucial tool for exploring and characterizing the structure properties of the molecular graphs, spectrum analysis and computation are flourishing in recent year. Let Ln be obtained from the tr...

In rule-based approaches, a model transformation definition tells how an instance of a source metamodel should be transformed to an instance of a target metamodel. As these metamodels undergo changes, model transformations defined over these metamodels may get out of sync. Restoring conformance between model transformations and the metamodels is a complex and error-prone task. In this paper, we propose a formal approach to automatically co-evolve model transformations according to the evolution of the metamodels. The approach is based on encoding the model transformation definition as a query-retyping combination and the evolution of the metamodels as applications of graph transformation rules. These rules are used to obtain an evolved query over the evolved metamodel together with a new retyping from the target metamodel. We will identify the criteria which need to be fulfilled in order to make this automatic co-evolution possible. We provide a tool support for this procedure, in which, from a traceability model that represents the original model transformation definition, we derive a co-evolved traceability model that represents the evolved transformation definition. Moreover, we use a case study to evaluate the approach with a set of commonly performed metamodel evolutions.

The Glasgow Subgraph Solver provides an implementation of state of the art algorithms for subgraph isomorphism problems. It combines constraint programming concepts with a variety of strong but fast domain-specific search and inference techniques, and is suitable for use on a wide range of graphs, including many that are found to be computationally hard by other solvers. It can also be equipped with side constraints, and can easily be adapted to solve other subgraph matching problem variants. We outline its key features from the view of both users and algorithm developers, and discuss future directions.

Directed bigraphs are a meta-model which generalises Milner’s bigraphs by taking into account the request flow between controls and names. A key problem about these bigraphs is that of bigraph embedding, i.e., finding the embeddings of a bigraph inside a larger one. We present an algorithm for computing embeddings of directed bigraphs, via a reduction to a constraint satisfaction problem. We prove soundness and completeness of this algorithm, and provide an implementation in jLibBig, a general Java library for manipulating bigraphical reactive systems, together with some experimental results.

International audience; Topology-based geometric modeling tackles the issue of representing objects with data structures that encode the topological subdivision of modeled objects in vertices, edges, faces, and volumes. Such subdivisions can be represented with graphs labeled by dimensions on arcs, while modeling operations used to edit the objects can be formalized as graph transformations. Among the existing topological models, we consider generalized and oriented maps, defined as constrained labeled graphs, to ensure the well-formedness of the represented objects. Since a modeling operation should provide a correct object when applied to a correct object, graph transformations are provided with conditions to ensure the model consistency. Our approach exploits the firmly established framework of DPO graph transformations to implement modeling operations. We enrich standard DPO graph transformations with a product construction to ease the operation design, enabling generic modeling operations as rule schemes. We lift conditions from DPO rules to this enriched framework, ensuring the preservation of the topological consistency via static analysis of syntactic conditions on rule schemes.

International audience; The Cloud computing paradigm has become the new industry standard way of designing large scale applications. Over the past years, we observe an increased adoption of this technology on numerous IoT-Edge applications. And while this technology comes with its promises and benefits, considering almost infinite scalability, it also comes along with its drawbacks and challenges. Detecting partial failures or bottlenecks are new obstacles that arose with the adoption of Cloud Applications. Distributed Tracing now allows developers to gain insight on the composition of services within a distributed Application. Today we observe an increased adoption of this technology on numerous cloud-native architectures. The project OpenTelemetry proposes a specification for traces that normalizes this new monitoring data format. In this publication we present an approach that leverages these traces to identify bottlenecks at the scale of a physically distributed application. We propose an extension of our model that builds a hierarchical property graph to exhibit bottlenecks in an application that follows the layered Cloud-IoT network model. Based on OpenTelemetry traces we can maintain a model at runtime of the whole application and compute bottlenecks. Their identification relies on the scores provided by centrality algorithms.

In this paper we describe our system for automatically extracting "correct" programs from proofs using a development for the Curry-Howard process. Although program extraction has been developed by many authors (see [5,?,?]), our system has a number of novel features designed to make it very easy to use and as close as possible to ordinary mathematical terminology and practice. These features include 1. the use of Henkin's technique [6] to reduce higher-order logic to many-sorted (first-order) logic 2. the free use of new rules for induction subject to certain conditions 3. the extensive use of previously programmed (primitive) recursive functions. 4. the use of templates to make the reasoning much closer to normal mathematical proffs. 5. an extension of the technique of the use of Harrop formulae to classically true formulae (cf. the footnote on p.101 in Kreisel [9]); As an example of our system we give a constructive proof of the well-known theorem that every graph of even parity, which is non-trivial in the sense that it does not consist of isolated vertices, has a cycle. Given such a graph as input, the extracted program produces a cycle as promised.

Constrained graph layout is a recent generalisation of force-directed graph layout which allows constraints on node placement. We give a constrained graph layout algorithm that takes an initial feasible layout and improves it while preserving the topology of the initial layout. The algorithm supports poly-line connectors and clusters. During layout the connectors and cluster boundaries act like impervious rubber-bands which try to shrink in length. The intended application for our algorithm is dynamic graph layout, but it can also be used to improve layouts generated by other graph layout techniques.

The paper summarises the contributions in a session at GCM 2019 presenting and discussing the use of native and translation-based solutions to common analysis problems for Graph Transformation Systems (GTSs). In addition to a comparison of native and translation-based techniques in this area, we explore design choices for the latter, s.a. choice of logic and encoding method, which have a considerable impact on the overall quality and complexity of the analysis. We substantiate our arguments by citing literature on application of theorem provers, model checkers, and SAT/SMT solver in GTSs, and conclude with a general discussion from a software engineering perspective, including comments from the workshop participants, and recommendations on how to investigate important design choices in the future., Comment: In Proceedings GCM 2019, arXiv:1912.08966

Dataflow Models of Computation (MoCs) are widely used in embedded systems, including multimedia processing, digital signal processing, telecommunications, and automatic control. In a dataflow MoC, an application is specified as a graph of actors connected by FIFO channels. One of the first and most popular dataflow MoCs, Synchronous Dataflow (SDF), provides static analyses to guarantee boundedness and liveness, which are key properties for embedded systems. However, SDF and most of its variants lacks the capability to express the dynamism needed by modern streaming applications. In particular, the applications mentioned above have a strong need for reconfigurability to accommodate changes in the input data, the control objectives, or the environment. We address this need by proposing a new MoC called Reconfigurable Dataflow (RDF). RDF extends SDF with transformation rules that specify how and when the topology and actors of the graph may be reconfigured. Starting from an initial RDF graph and a set of transformation rules, an arbitrary number of new RDF graphs can be generated at runtime. A key feature of RDF is that it can be statically analyzed to guarantee that all possible graphs generated at runtime will be consistent and live. We introduce the RDF MoC, describe its associated static analyses, and present its implementation and some experimental results.; Les modèles de calcul (MoCs) flot de données synchrones sont très utilisés dans les systèmes embarqués et les applications multimédia, de traitement du signal, de télécommunication et de contrôle automatique. Dans ce style de modèle, une application est spécifiée par un graphe d’acteurs connectés par des liens FIFO de communication. Un des MoCs les plus connus, SDF (pour Synchronous Dataflow), permet des analyses statiques qui garantissent l’exécution en mémoire bornée et l’absence d’interblocage, propriétés clés pour les systèmes embarqués. Néanmoins, SDF (et la plupart de ses variantes) ne permet pas d’exprimer la dynamicité requise par les applications embarquées modernes. En particulier, ces applications ont souvent besoin de se reconfigurer pour s’adapter aux changements (par ex., de débit ou de qualité) du flot d’entrée, des objectifs de contrôle ou de l’environnement. Afin de répondre à ce besoin, nous proposons RDF (pour Reconfigurable DataFlow) un MoC qui étend SDF avec des règles de transformations spécifiant comment la topologie du graphe flot de données peut être reconfiguré dynamiquement. En considérant un graphe SDF initial et un ensemble de règles de transformation, un nombre arbitraire de nouveaux graphes peuvent être produits. La principale qualité de RDF est qu’il peut être analysé statiquement pour garantir que tous les graphes générés dynamiquement s’exécuteront en mémoire bornée et sans interblocage. Nous présentons le modèle RDF, les analyses statiques associées, sa mise en oeuvre et quelques expérimentations.

Designing and reasoning about complex systems such as wireless sensor networks is hard due to highly dynamic environments: sensors are heterogeneous, battery-powered, and mobile. While formal modelling can provide rigorous mechanisms for design/reasoning, they are often viewed as difficult to use. Graph rewrite-based modelling techniques increase usability by providing an intuitive, flexible, and diagrammatic form of modelling in which graph-like structures express relationships between entities while rewriting mechanisms allow model evolution. Two major graph-based formalisms are Graph Transformation Systems (GTS) and Bigraphical Reactive Systems (BRS). While both use similar underlying structures, how they are employed in modelling is quite different. To gain a deeper understanding of GTS and BRS, and to guide future modelling, theory, and tool development, in this experience report we compare the practical modelling abilities and style of GTS and BRS when applied to topology control in WSNs. To show the value of the models, we describe how analysis may be performed in both formalisms. A comparison of the approaches shows that although the two formalisms are different, from both a theoretical and practical modelling standpoint, they are each successful in modelling topology control in WSNs. We found that GTS, while featuring a small set of entities and transformation rules, relied on entity attributes, rule application based on attribute/variable side-conditions, and imperative control flow units. BRS on the other hand, required a larger number of entities in order to both encode attributes directly in the model (via nesting) and provide tagging functionality that, when coupled with rule priorities, implements control flow. There remains promising research mapping techniques between the formalisms to further enable flexible and expressive modelling.

Capturing human knowledge underlying the design and engineering of products has been among the main goals of computational engineering since its very beginning. Over the last decades, various approaches have been proposed to tackle this objective. Among the most promising approaches is the application of graph theory for representing product structures by defining nodes representing entities and edges representing relations among them. The concrete meaning of these structures ranges from geometry representations over hierarchical product breakdowns to functional descriptions and flows of information or resources. On top of these graph structures, graph rewriting techniques provide another powerful layer of technology. By enabling the formal definition of rules for transforming graph structures, they allow on the one hand side to formally capture the engineering development process. On the other hand, the assembly of rewriting rules into graph grammars allows for an exhaustive search of the solution space of the engineering problem at hand. In combination with search strategies, an automated optimization of the design under given constraints and objectives can be realized. The paper provides an overview of the current state-of-the-art in graph rewriting and its applications in engineering design, with a focus on the built environment. It concludes with a discussion of the progress achieved and the missing research gaps.

International audience; Cloud-Applications are the new industry standard way of designing Web-Applications. With Cloud Computing, Applications are usually designed as microservices, and developers can take advantage of thousands of such existing microservices, involving several hundred of cross-component communications on different physical resources. Microservices orchestration (as Kubernetes) is an automatic process, which manages each component lifecycle, and notably their allocation on the different resources of the cloud infrastructure. Whereas such automatic cloud technologies ease development and deployment, they nevertheless obscure debugging and performance analysis. In order to gain insight on the composition of services, distributed tracing recently emerged as a way to get the decomposition of the activity of each component within a cloud infrastructure. This paper aims at providing methodologies and tools (leveraging state-of-the-art tracing) for getting a wider view of application behaviours, especially focusing on application performance assessment. In this paper, we focus on using distributed traces and allocation information from microservices to model their dependencies as a hierarchical property graph. By applying graph rewriting operations, we managed to project and filter communications observed between microservices at higher abstraction layers like the machine nodes, the zones or regions. Finally, in this paper we propose an implementation of the model running on a microservices shopping application deployed on a Zonal Kubernetes cluster monitored by OpenTelemetry traces. We propose using the flow hierarchy metric on the graph model to pinpoint cycles that reveal inefficient resource composition inducing possible performance issues and economic waste.

This work is licensed under a Creative Commons Attribution 4.0 International License. Models@runtime (models at runtime) are based on computation reflection. Runtimemodels can be regarded as a reflexive layer causally connected with the underlying system. Hence,every change in the runtime model involves a change in the reflected system, and vice versa. Tothe best of our knowledge, there are no runtime models for Python applications. Therefore, wepropose a formal approach based on Petri Nets (PNs) to model, develop, and reconfigure Pythonapplications at runtime. This framework is supported by a tool whose architecture consists of twomodules connecting both the model and its execution. The proposed framework considers executionexceptions and allows users to monitor Python expressions at runtime. Additionally, the applicationbehavior can be reconfigured by applying Graph Rewriting Rules (GRRs). A case study usingService-Level Agreement (SLA) violations is presented to illustrate our approach. 11 20

The declarative graph transformation language Henshin transforms instance models represented as graphs by applying a series of basic steps that match and replace structural patterns on parts of models. These simple transformation rules are then combined into control flow constructs similar to those of imperative programming languages to create more complex transformations. However, defects in the structure of control flow or in transformation rules might misschedule the application of operations, resulting in basic steps to be inapplicable or produce incorrect output. Understanding and fixing these bugs is complicated by the fact that pattern matching in rules is non-deterministic. Moreover, some control flow structures employ a nondeterministic choice of alternatives. This makes it challenging for developers to keep track of all the possible execution paths and interactions between them. For conventional programming languages, techniques have been developed to execute a program symbolically. By abstracting over the concrete values of variables in any actual run, generalized knowledge is gained about the possible behavior of the program. This can be useful in understanding problems and fixing bugs. In this paper, we present an approach to symbolically execute graph transformations for a subset of Henshin, using symbolic path constraints based on the cardinalities of graph pattern occurrences in the model.

With the constant research and development of Transactional Memory (TM) systems, various algorithms have been proposed, and their correctness is always an important aspect to take into account. When analyzing TM algorithms, one of the most commonly used correctness criterion is opacity, which infers that the algorithm only generates executions that observe consistent states of the shared memory. In this work we present a formal definition to demonstrate that a given TM algorithm only generates opaque histories using a Graph Transformation System (GTS). We achieve that by introducing a methodology of translating an algorithm into production rules that manipulate the state of a graph. With a set initial state of transactions, the result of this method consists of a state space that includes every possible order of execution of transactional operations that are automatically checked for opacity, therefore all possible histories the algorithm can generate are checked for the safety property. As a case study we demonstrate our approach using the algorithm CaPR+.

One way to implement model-based software product lines (MBSPLs) is to use a transformational approach known as Delta Modeling (DM). Here, an MBSPL is implemented by one core model and a set of delta modules. Delta modules define model transformations using edit operations which add, remove or modify model elements. Editings of different delta modules can be in conflict or depend on each other, leading to conflict and dependency relations between delta modules. Conflicts and unfulfilled dependencies can cause the generation of a product to fail or to lead to invalid models. In order to spot such defects, one needs analysis tools for each modeling (sub-)language used. Existing generic approaches to statically detect such defects in a language-agnostic manner analyze pairs of delta modules. However, the pairwise approach can lead to false positives, i.e., conflicts and unfulfilled dependencies are reported although product generation does not fail. Following the idea of family-based analysis, this paper presents a new approach to detect pseudo defects resolved by "healing effects" implied by the network of dependencies. These effects typically occur when a delta module (partially) reverts the effect of a preceding delta module. We have implemented our approach within the SiPL framework and evaluated our family-based analysis using a realistic MBSPL known as Body Comfort System (BCS).

Purpose Graph rewriting concerns the technique of transforming a graph; it is thus natural to conceive its application in the evolution of graph databases. This paper aims to propose a two-step framework where rewriting rules formalize instance or schema changes, ensuring graph’s consistency with respect to constraints, and updates are managed by ensuring rule applicability through the generation of side effects: new updates which guarantee that rule application conditions hold. Design/methodology/approach This paper proposes Schema Evolution Through UPdates, optimized version (SetUpOPT), a theoretical and applied framework for the management of resource description framework (RDF)/S database evolution on the basis of graph rewriting rules. The framework is an improvement of SetUp which avoids the computation of superfluous side effects and proposes, via SetUpoptND, a flexible and extensible package of solutions to deal with non-determinism. Findings This paper shows graph rewriting into a practical and useful application which ensures consistent evolution of RDF databases. It introduces an optimised approach for dealing with side effects and a flexible and customizable way of dealing with non-determinism. Experimental evaluation of SetUpoptND demonstrates the importance of the proposed optimisations as they significantly reduce side-effect generation and limit data degradation. Originality/value SetUp originality lies in the use of graph rewriting techniques under the closed world assumption to set an updating system which preserves database consistency. Efficiency is ensured by avoiding the generation of superfluous side effects. Flexibility is guaranteed by offering different solutions for non-determinism and allowing the integration of customized choice functions.

International audience; This paper describes a system proposed for the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (EUD). We propose a Graph Rewriting based system for computing Enhanced Universal Dependencies, given the Basic Universal Dependencies (UD).

Technological innovations in data science and artificial intelligence research have led to increasing task automation in autonomous driving. Currently, most test engineering processes in the industry are based on manual test case specification and the accumulation of certain test mile thresholds. This test engineering is very cost- and time-consuming. But especially the test case specification and selection is influenced by human bias. A promising potential approach to overcome those drawbacks is data-driven test case mining based on big data of sensor/actor recordings from real driving situations. The key challenge for data-driven test case mining, is handling the huge amount of data generated by the car sensors related to the open-world context of autonomous driving. This paper presents a novel data-driven approach to quantify events and situations which occur during recorded test drives by transforming multivariate time series data into a condensed, directed graph. This graphical model makes such events and situations comparable and enables the application of established coverage criteria and thus supports statistical statements regarding the coverage of potentially infinite operating environments. To illustrate the benefits of this approach, we conducted a quantitative evaluation in an industrial context in the domain of automated driving, including over 1000 km of field data. The overall results prove that a significant amount of the data characteristics do not get lost during the Graph transformation.

International audience; Forest characterization at tree scale is possible with remotely sensed images of high spatial resolution. A first step is the Individual Tree Crown (ITC) delineation which corresponds to the segmentation of canopy cover into different tree crowns. In this study, a new method based on an initial watershed segmentation of Canopy Height Model (CHM) is proposed. This method is based on a graph transformation of the initial segmentation map in order to apply structural criteria (calculated owning to CHM) and spectral criterion (computed on red, green and blue bands). Adaptive thresholds are defined according to the studied forest characteristics in order to improve low quality segmentation cases. This method has been applied on a complex forest site (Broadleaf dominant, steep relief…). The results show a 17% increase of global performance in comparison to the reference watershed segmentation.; La caractérisation de la forêt à l'échelle de l'arbre est possible avec des images de télédétection de haute résolution spatiale. Une première étape est la délimitation de la couronne individuelle des arbres (ITC) qui correspond à la segmentation du couvert forestier en différentes couronnes d'arbres. Dans cette étude, une nouvelle méthode basée sur une segmentation initiale des bassins versants du modèle de hauteur de la canopée (CHM) est proposée. Cette méthode est basée sur une transformation graphique de la carte de segmentation initiale afin d'appliquer des critères structurels (calculés en propriété au CHM) et spectraux (calculés sur des bandes rouges, vertes et bleues). Des seuils adaptatifs sont définis en fonction des caractéristiques forestières étudiées afin d'améliorer les cas de segmentation de faible qualité. Cette méthode a été appliquée sur un site forestier complexe (dominante feuillue, relief escarpé…). Les résultats montrent une augmentation de 17% de la performance globale par rapport à la segmentation des bassins versants de référence.