Search

We present a new and powerful algebraic framework for graph rewriting, based on drags, a class of graphs enjoying a novel composition operator. Graphs are embellished with roots and sprouts, which can be wired together to form edges. Drags enjoy a rich algebraic structure with sums and products. Drag rewriting naturally extends graph rewriting, dag rewriting, and term rewriting models.

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.

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.

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.

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).

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.

International audience; This article presents a set of tools built around the Graph Rewriting computational framework which can be used to compute complex rule-based transformations on linguistic structures. Application of the graph matching mechanism for corpus exploration, error mining or quantitative typology are also given.

In this work, we introduce KnitKit , a flexible and customizable system for the computational design and production of functional, multi-material, and three-dimensional knitted textiles. Our system greatly simplifies the knitting of 3D objects with complex, varying patterns that use multiple yarns and stitch patterns by separating the high-level design specification in terms of geometry, stitch patterns, materials or colors from the low-level, machine-specific knitting instruction generation. Starting from a triangular 3D mesh and a 2D texture that specifies knitting patterns on top of the geometry, our system generates the required machine instructions in three major steps. First, the input is processed and the KnitNet data structure is generated. This graph structure serves as an abstract interface between the high-level geometric and knitting configuration and the low-level, machine-specific knitting instructions. Second, a graph rewriting procedure is applied on the KnitNet that produces a sequence of abstract machine actions. Finally, the low-level machine instructions are generated by adapting those abstract actions to a specific machine context. We showcase the potential of this computational approach by designing and fabricating a variety of objects with complex geometries, multiple yarns, and multiple stitch patterns.

13th International Workshop, WRLA 2020, Virtual Event, October 20-22, 2020, Revised Selected Papers; International audience; We define two graph transformations, one by parallelizing graph rewrite rules, the other by taking quotients of graphs. The former consists in the exhaustive application of local transformations defined by graph rewrite rules expressed in a set-theoretic framework. Compared with other approaches to parallel rewriting, we allow a substantial amount of overlapping only restricted by a condition called the effective deletion property. This transformation can be reduced by factoring out possibly many equivalent matchings by the automorphism groups of the rules. The second transformation is based on the use of equivalence relations over graph items and offers a new way of performing simultaneous merging operations. The relevance of combining the two transformations is illustrated on a running example.

We consider the recommendations of the World Wide Web Consortium (W3C) about RDF framework and its associated query language SPARQL. We propose a new formal framework based on category theory which provides clear and concise formal definitions of the main basic features of RDF and SPARQL. We define RDF graphs as well as SPARQL basic graph patterns as objects of some nested categories. This allows one to clarify, in particular, the role of blank nodes. Furthermore, we consider basic SPARQL CONSTRUCT and SELECT queries and formalize their operational semantics following a novel algebraic graph transformation approach called POIM., Comment: In Proceedings GCM 2020, arXiv:2012.01181. arXiv admin note: substantial text overlap with arXiv:1910.07519

We present a proof-theoretic analysis of the logic NLλ (Barker & Shan 2014, Barker 2019). We notably introduce a novel calculus of proof nets and prove it is sound and complete with respect to the sequent calculus for the logic. We study decidability and complexity of the logic using this new calculus, proving a new upper bound for complexity of the logic (showing it is in NP) and a new lower bound for the class of formal language generated by the formalism (mildly context-sensitive languages extended with a permutation closure operation). Finally, thanks to this new calculus, we present a novel comparison between NLλ and the hybrid type-logical grammars of Kubota & Levine (2020). We show there is an unexpected convergence of the natural language analyses proposed in the two formalism. In addition to studying the proof-theoretic properties of NLλ, we greatly extends its linguistic coverage.

In this paper, we combine ideas from two different scientific traditions: 1) graph transformation systems (GTSs) stemming from the theory of formal languages and concurrency, and 2) mean field approximations (MFAs), a collection of approximation techniques ubiquitous in the study of complex dynamics. Using existing tools from algebraic graph rewriting, as well as new ones, we build a framework which generates rate equations for stochastic GTSs and from which one can derive MFAs of any order (no longer limited to the humanly computable). The procedure for deriving rate equations and their approximations can be automated. An implementation and example models are available online at https://rhz.github.io/fragger. We apply our techniques and tools to derive an expression for the mean velocity of a two-legged walker protein on DNA., Comment: to be presented at the 18th International Conference on Computational Methods in Systems Biology (CMSB 2020)

The task of automatically extracting insights or building computational models fromknowledge on complex systems greatly relies on the choice of appropriate representation.This work makes an effort towards building a framework suitable for representation offragmented knowledge on complex systems and its semi-automated curation---continuouscollation, integration, annotation and revision.We propose a knowledge representation system based on hierarchies of graphs relatedwith graph homomorphisms. Individual graphs situated in such hierarchies representdistinct fragments of knowledge and the homomorphisms allow relating these fragments.Their graphical structure can be used efficiently to express entities and their relations. Wefocus on the design of mathematical mechanisms, based on algebraic approaches to graphrewriting, for transformation of individual graphs in hierarchies that maintain consistentrelations between them. Such mechanisms provide a transparent audit trail, as well as aninfrastructure for maintaining multiple versions of knowledge.We describe how the developed theory can be used for building schema-aware graphdatabases that provide schema-data co-evolution capabilities. The proposed knowledgerepresentation framework is used to build the KAMI (Knowledge Aggregation and ModelInstantiation) framework for curation of cellular signalling knowledge. The frameworkallows for semi-automated aggregation of individual facts on protein-protein interactionsinto knowledge corpora, reuse of this knowledge for instantiation of signalling models indifferent cellular contexts and generation of executable rule-based models., L'extraction automatique des intuitions et la construction de modèles computationnels à partir de connaissances sur des systèmes complexes repose largement sur le choix d'une représentation appropriée. Ce travail s'efforce de construire un cadre adapté pour la représentation de connaissances fragmentées sur des systèmes complexes et sa curation semi-automatisé.Un système de représentation des connaissances basé sur des hiérarchies de graphes liés à l'aide d'homomorphismes est proposé. Les graphes individuels représentent des fragments de connaissances distincts et les homomorphismes permettent de relier ces fragments. Nous nous concentrons sur la conception de mécanismes mathématiques,basés sur des approches algébriques de la réécriture de graphes, pour la transformation de graphes individuels dans des hiérarchies qui maintient des relations cohérentes entre eux.De tels mécanismes fournissent une piste d'audit transparente, ainsi qu'une infrastructure pour maintenir plusieurs versions des connaissances.La théorie développée est appliquée à la conception des schémas pour les bases de données orientée graphe qui fournissent des capacités de co-évolution schémas-données.Ensuite, cette théorie est utilisée dans la construction du cadre KAMI, qui permet la curation des connaissances sur la signalisation dans les cellules. KAMI propose des mécanismes pour une agrégation semi-automatisée de faits individuels sur les interactions protéine-protéine en corpus de connaissances, la réutilisation de ces connaissances pour l'instanciation de modèles de signalisation dans différents contextes cellulaires et la génération de modèles exécutables basés sur des règles.

Kinetic transition networks (KTNs) of local minima and transition states are able to capture the dynamics of numerous systems in chemistry, biology, and materials science. However, extracting observables is numerically challenging for large networks and generally will be sensitive to additional computational discovery. To have any measure of convergence for observables, these sensitivities must be regularly calculated. We present a matrix formulation of the discrete path sampling framework for KTNs, deriving expressions for branching probabilities, transition rates, and waiting times. Using the concept of the quasi-stationary distribution, a clear hierarchy of expressions for network observables is established, from exact results to steady-state approximations. We use these results in combination with the graph transformation method to derive the sensitivity, with respect to perturbations of the known KTN, giving explicit terms for the pairwise sensitivity and discussing the pathwise sensitivity. These results provide guidelines for converging the network, with respect to additional sampling, focusing on the estimates obtained for the overall rate coefficients between product and reactant states. We demonstrate this procedure for transitions in the double-funnel landscape of the 38-atom Lennard-Jones cluster.

Graph canonization (that solves also the graph isomorphism question) is an old problem that still attracts a lot of attention today, mainly because of the ubiquitous aspect of graph-based structures in computer science applications. This article present the proofs of correctness for the SCOTT algorithm, a graph canonization algorithm designed to provide a Canonical form for general graphs, namely graphs for which vertices and edges are coloured (labelled). These proofs ensure that the three canonical forms provided by SCOTT are valid, namely a canonical adjacency matrix, a canonical rooted tree (or DAG) and a canonical string. In addition, some crude lower and upper complexity bounds are presented and discussed. Finally some empirical evaluation is provided on a difficult synthetic benchmark with some comparison with the state of the art algorithms.

International audience; This paper presents an approach to automatically and transparently parallelize algorithms to build 2D or 3D virtual objects in geometric modeling: In particular, we show that subdivision and Iterated Function System constructions can be parallelized, without any explicit parallelization study by their developer. These operations are described in the framework Jerboa, where each operation is expressed as a graph transformation and objects are topologically described using generalized maps. All transformations are handled by a generic engine that can handle structure changes in parallel. The obtained results allow any designer of virtual environments to rely on modern multi-core and multi-processor architectures to get faster constructions of complex objects without any skills on parallelism.

The termination issue we tackle is rooted in natural language processing where graph rewriting systems (GRS) may contain a large number of rules, often in the order of thousands. Decidable concepts thus become mandatory to verify the termination of such systems. The notion of graph rewriting consider does not make any assumption on the structure of graphs (they are not “term graphs”, “port graphs” nor drags). The lack of algebraic structure in our setting led us to proposing two orders on graphs inspired from language theory: the matrix multiset-path order and the rational embedding order. We show that both are stable by context, which we then use to obtain the main contribution of the paper: under a suitable notion of “interpretation”, a GRS is terminating if and only if it is compatible with an interpretation.

International audience; Graph transformation is a specification technique suitable for a wide range of applications, specially the ones that require a sophisticated notion of state. In graph transformation, states are represented by graphs and actions are specified by rules. Most algebraic approaches to graph transformation proposed in the literature ensure that if an item is preserved by a rule, so are its connections with the graph where it is embedded. But there are applications in which it is desirable to specify different embeddings. For example when cloning an item, there may be a need to handle the original and the copy in different ways. We propose a new algebraic approach to graph transformation, AGREE: Algebraic Graph Rewriting with controllEd Embedding, where rules allow one to specify how the embedding should be carried out. We define this approach in the framework of classified categories which are categories endowed with partial map classifiers. This new approach leads to graph transformations in which effects may be non-local, e.g. a rewrite step may alter a node of the host graph which is outside the image of the left-hand side of the considered rule. We propose a syntactic condition on AGREE rules which guarantees the locality of transformations. We also compare AGREE with other algebraic approaches to graph transformation.

International audience; Graphs increasingly stand out as an essential data structurein the field of data sciences. To study graphs, or sub-graphs, that char-acterize a set of observations, it is necessary to describe them formally,in order to characterize equivalence relations that make sense in thescope of the considered application domain. Hence we seek to define acanonical graph notation, so that two isomorphic (sub) graphs have thesame canonical form. Such notation could subsequently be used to indexand retrieve graphs or to embed them efficiently in some metric space.Sequential optimized algorithms solving this problem exist, but do notdeal with labeled edges, a situation that occurs in important applicationdomains such as chemistry. We present in this article a new algorithmbased on graph rewriting that provides a general and complete solution tothe graph canonization problem. Although not reported here, the formalproof of the validity of our algorithm has been established. This claim isclearly supported empirically by our experimentation on synthetic com-binatorics as well as natural graphs. Furthermore, our algorithm supportsdistributed implementations, leading to efficient computing perspectives.

National audience; We present GREW, a tool dedicated to corpus annotation and the exploitation of annotated corpora. Based on graph rewriting, it can be used to search for patterns in annotated data and to transform this type of data.; Nous présentons GREW, un outil dédié à l'annotation de corpus et à l'exploitation de corpus annotés. Fondé sur la réécriture de graphes, il peut être utilisé d'une part pour rechercher des motifs dans des données annotées et d'autre part pour transformer ce type de données.

Recruté maître de conférences en septembre 2008, je suis membre de l’équipe BKB (Bench to Knowledge and Beyond) du Laboratoire Bordelais de Recherche en Informatique (LaBRI) et responsable du thème « Model Analysis to Knowledge ». Le nom du thème résume parfaitement la thématique générale de mes travaux qui se situent dans ce que l’on appelle dorénavant la « science des données ». Cette science, en plein essor, consiste à utiliser de façon combinée et complémentaire des outils mathématiques, statistiques, de l’informatique et de la visualisationd’informations pour permettre à un expert d’un domaine d’application d’analyser ses données complexes et hétérogènes mais pas forcément volumineuses (les données tiennent en mémoire centrale d’un ordinateur moderne). L’objectif principal est d’améliorer sa compréhension des données et de leurs relations et ainsi potentiellement extraire des nouvelles connaissances intéressantes. Dans ce contexte mes travaux se focalisent globalement sur la modélisation, construction, stockage, visualisation et analyse de divers types de réseaux construits à l’aide de données fournies, le plus souvent, par des experts de ces données. Dans ce manuscrit, je présente des collaborations avec des géographes, juristes, bioinformaticiens, historiens, et pour finir avec des experts en sciences forensiques ou criminelles.Dans mon cas, un réseau est défini informellement comme un ensemble d’éléments liés entre eux ou en interactions. Mathématiquement parlant, un réseau est modélisé par un graphe qu’il faut construire, manipuler et visualiser. Depuis que je suis au LaBRI, la majeure partie de mestravaux est consacrée à une mise en œuvre particulière du processus décrit précédemment : le développement d’une méthodologie basée sur la programmation à base de règles, aussi appelée réécriture de graphes, et de son implémentation dans une plateforme visuelle et interactivebaptisée Porgy. L’objectif est de construire un modèle d’un système complexe, d’effectuer des simulations variées et d’analyser les résultats obtenus le tout en utilisant la visualisation et en interaction permanente avec l’expert des données. J’ai aussi notamment contribué à des travaux sur la visualisation de graphes ou l’évaluation quantitative et qualitative de méthodes de visualisation.La construction et/ou la manipulation et/ou la visualisation d’un réseau sont toujours présentes dans mes travaux et mes publications portent sur tout ou partie de ce processus. Je retiens particulièrement 7 articles dans des journaux internationaux, 6 articles dans des conférences internationales, 3 chapitres de livres internationaux, 3 publications à portée nationale (dont un prix du meilleur article académique en 2015). Ces contributions ont été pour la plupart rendues possible par la coordination de deux projets ANR (jeunes chercheurs et international avec leLuxembourg) et deux co-directions de thèse (la première soutenue en décembre 2017 et l’autre débutée en avril 2016). Ces travaux possèdent, bien sûr, une part importante de développement logiciels. Les travaux sur Porgy sont liés à des collaborations nationales et internationales initiées rapidement après ma nomination MCF en 2008.Dans ce manuscrit, après une introduction qui détaille le positionnement scientifique et le contexte de l’ensemble de mes travaux et leurs contributions, je présente dans deux chapitres la plateforme Porgy et sa méthodologie de programmation à base de règles. Le premier porte surla conception et le développement de l’ensemble de la méthodologie et de l’outil Porgy pour en faire une plateforme générique, c’est-à-dire non dédiée à un type de donnée particulière. Le deuxième chapitre présente différentes applications de Porgy afin de montrer que la plateformeet sa méthodologie associée possèdent bien les propriétés annoncées comme la généricité, la souplesse (applications sur des données bioinformatique ou bien des réseaux sociaux) et couvre l’ensemble des étapes d’un processus de science des données : modélisation, simulation et analyse.Plus récemment, je participe à des projets en collaboration avec des experts de sciences humaines et sociales (géographie, histoire contemporaine, réseaux criminels, humanités numériques). Mon objectif premier reste sensiblement le même que pour les travaux sur Porgy : àpartir de données complexes et hétérogènes fournies par les experts, il s’agit de (re)construire et analyser visuellement et interactivement des réseaux pour aider l’expert dans sa compréhension des données. Je présente dans un dernier chapitre des leçons tirées de ces projets notammentla difficulté de trouver un modèle générique de réseau suffisamment souple pour s’adapter à tous les types d’application et d’interactions. En particulier, un système complexe réel ne se modélise pas seulement avec un seul réseau mais plutôt un ensemble de réseaux liés entre eux.Une réponse semble être l’utilisation d’un modèle récemment publié (2014) baptisé les réseaux multicouches. Ce modèle permet de vraiment prendre en compte l’ensemble de la complexité du système à modéliser tout en restant facilement compréhensible et manipulable par les expertsdes données. La notion de couches amène des questions nouvelles puisque celles-ci deviennent un artefact mobilisable par l’analyse et la visualisation. Ces techniques d’analyse et de visualisation doivent donc évoluer pour être adaptées aux réseaux multicouches. Ce manuscrit termine ainsi par différentes perspectives de recherche autour des réseaux multicouches et de la confiance, si difficile à obtenir, des experts dans la visualisation.

This paper presents a method for verifying graph transformation programs written in Small-t\(\mathcal ALC\), an imperative language which allows expressing graph properties and graph transformations in \(\mathcal ALCQI\) description logic. We aim at reasoning not only about the local effect when applying a transformation rule on a matched subgraph but also about the global impact on the whole input graph when applying a set of rules. Using \(\mathcal ALCQI\) assertional and terminological formulae to formalize directed labeled graphs, Small-t\(\mathcal ALC\) allows specifying local properties on individual nodes and edges as well as global properties on sets of nodes and edges. Our previous work focuses on verifying local properties of the graph. In this paper, we propose a static analyzer at terminological level that intertwines with a static analyzer at assertional level to infer global properties of the transformed graph.

International audience; The ability of 3D modeling tools to generate automatically various versions of a similar model is an increasing need in several and diferent domains such as Archaeology, Architecture or Geology. To address this issue, we propose to use both the Jerboa library designed to assist the development of application-specific modelers and the reevaluation methods used for parametric systems in the CAD domain. Unlike most approaches, Jerboa is independent from any application domain and allows rapid development of new operations using graph transformation rules to automatically check the consistency of different objects properties. But it do es not support any reevaluation mechanism and especially not a persistent naming system , that is used to identify entities of the initial model and match them with entities of the reevaluated model. Using the capacity of graph transformation rules, we address naming problems through a very precise characterization of the basic elements forming the model.

A mathematical theory is presented for the representation of knowledge in the form of a directed acyclic hierarchy of objects in a category where all paths between any given pair of objects are required to be equal. The conditions under which knowledge update, in the form of the sesqui-pushout rewriting of an object in a hierarchy, can be propagated to the rest of the hierarchy, in order to maintain all required path equalities, are analysed: some rewrites must be propagated forwards, in the direction of the arrows, while others must be propagated backwards, against the direction of the arrows, and, depending on the precise form of the hierarchy, certain composability conditions may also be necessary. The implementation of this theory, in the ReGraph Python library for (simple) directed graphs with attributes on nodes and edges, is then discussed in the context of two significant use cases., 25 pages, 4 figures, submitted to the Journal of Logical and Algebraic Methods in Programming

Thomas's necessary conditions for the existence of multiple steady states in gene networks have been proved by Soul\'e with high generality for dynamical systems defined by differential equations. When applied to (protein) reaction networks however, those conditions do not provide information since they are trivially satisfied as soon as there is a bimolecular or a reversible reaction. Refined graphical requirements have been proposed to deal with such cases. In this paper, we present for the first time a graph rewriting algorithm for checking the refined conditions given by Soliman, and evaluate its practical performance by applying it systematically to the curated branch of the BioModels repository. This algorithm analyzes all reaction networks (of size up to 430 species) in less than 0.05 second per network, and permits to conclude to the absence of multistationarity in 160 networks over 506. The short computation times obtained in this graphical approach are in sharp contrast to the Jacobian-based symbolic computation approach. We also discuss the case of one extra graphical condition by arc rewiring that allows us to conclude on 20 more networks of this benchmark but with a high computational cost. Finally, we study with some details the case of phosphorylation cycles and MAPK signalling models which show the importance of modelling the intermediate complexations with the enzymes in order to correctly analyze the multistationarity capabilities of such biochemical reaction networks., Comment: Journal of Theoretical Biology, Elsevier, In press

International audience; This article proposes a surface-syntactic annotation scheme called SUD that is near-isomorphic to the Universal Dependencies (UD) annotation scheme while following distributional criteria for defining the dependency tree structure and the naming of the syntactic functions. Rule-based graph transformation grammars allow for a bi-directional transformation of UD into SUD. The back-and-forth transformation can serve as an error-mining tool to assure the intra-language and inter-language coherence of the UD treebanks.

International audience; GPaR is a parallel graph rewriting software implemented in C++ with a graphical user interface. Considering an initial graph $g$ and a system of rewriting rules $R = \{l_i \to r_i; i = 1 \dots n\}$, GPaR rewrites the graph $g$ into a graph $g'$ by using, simultaneously, the rules of $R$ whose left-hand sides, $l_i$, match subgraphs of $g$. GPaR tackles the problem of overlapping matches and thus can be used in a large variety of rewritingproblems including fractal systems. Our proposition is illustrated on the examples of adaptive mesh and Pythagorean tree. The performance of GPaR is compared to the performance of other tools on the Sierpinski triangle benchmark.

A very large amount of work in Natural Language Processing (NLP) use tree structure as the first class citizen mathematical structures to represent linguistic structures, such as parsed sentences or feature structures. However, some linguistic phenomena do not cope properly with trees; for instance, in the sentence ‘Max decides to leave,’ ‘Max’ is the subject of the both predicates ‘to_decide’ and ‘to_leave’. Tree-based linguistic formalisms generally use some encoding to manage sentences like the previous example. In former papers (Bonfante et al. 2011; Guillaume and Perrier 2012), we discussed the interest to use graphs rather than trees to deal with linguistic structures, and we have shown how Graph Rewriting could be used for their processing, for instance in the transformation of the sentence syntax into its semantics. Our experiments have shown that Graph Rewriting applications to NLP do not require the full computational power of the general Graph Rewriting setting. The most important observation is that all graph vertices in the final structures are in some sense ‘predictable’ from the input data, and so we can consider the framework of Non-size increasing Graph Rewriting. In our previous papers, we have formally described the Graph Rewriting calculus we used and our purpose here is to study the theoretical aspect of termination with respect to this calculus. Given that termination is undecidable in general, we define termination criterions based on weight, we prove the termination of weighted rewriting systems, and we give complexity bounds on derivation lengths for these rewriting systems.

International audience; We propose to use strategic port-graph rewriting as a visual modelling tool to analyse credit derivative markets. We illustrate the approach by specifying a basic " rational negligence " model in which investors may choose to trade securities without performing independent evaluations of the underlying assets. We show that our model is correct with respect to the equational model and can be used to simulate simple market behaviours. The model has been implemented within PORGY, a graph-based specification and simulation environment.

International audience; Inlining is an important optimization technique in any modern compiler, though the description of this technique in the literature is informal and vague. We describe a technique for inlining, designed to work on a flow graph of instructions of intermediate code. Our technique uses local graph rewriting, making the semantic correctness of this technique obvious. In addition, we prove that the algorithm terminates. As a direct result of the preservation of the semantics of the program after each local rewriting step, the algorithm can stop after any iteration, resulting in a partial inlining of the called function. Such partial inlining can be advantageous in order to avoid the inlining of code that is not performance critical, in particular for creating arguments and calls to error-signaling functions.

International audience; We present TESTOR, a tool for on-the-fly conformance test case generation, guided by test purposes. Concretely, given a formal specification of a system and a test purpose, TESTOR automatically generates test cases, which assess using black box testing techniques the conformance to the specification of a system under test. In this context, a test purpose describes the goal states to be reached by the test and enables one to indicate parts of the specification that should be ignored during the testing process. Compared to the existing tool TGV, TESTOR has a more modular architecture, based on generic graph transformation components , is capable of extracting a test case completely on the fly, and enables a more flexible expression of test purposes, taking advantage of the multiway rendezvous. TESTOR has been implemented on top of the CADP verification toolbox, evaluated on three published case-studies and more than 10000 examples taken from the non-regression test suites of CADP.

3D modeling for Archaeology requires to easily model scenes by letting users evaluate a parametric specification of archaeology-oriented gestures, then modify and reevaluate the specification to produce various restitution hypotheses. But the current modeling tools that support reevaluation mechanisms are not dedicated to Archaeology. The Jerboa library, based on graph transformations rules, is well suited for creating operations fitting the needs of archaeologists. But it does not any support reevaluation mechanism and especially the persistent naming system, that is used to identify the entities of the initial model and match them with entities of the reevaluated model. In this paper, we extend Jerboa with a new application-independent persistent naming model, which is more general and homogeneous than other solutions found in the literature and is the first one to handle parametric specification edition.

Remote connectivity of today’s and future cars increases their capabilities of autonomy and safety, but also their attack surface, as reported by several research papers. In the automotive domain, the security has a direct impact on the user’s safety. Thus, the management of risk is becoming the main concern of automotive manufacturers, especially for the future fully connected and autonomous cars. A possible way to quantify the overall risk of a system is the systematic construction of attack graphs and attack trees. These formalisms are presented as one of the possible solutions in the new Cybersecurity Guidebook for Cyber-Physical Vehicle Systems (SAE-J3061). In this chapter we propose to use graph transformation to formally model the car architecture and its state evolution in order to study cyber-physical attacks against it. The resulting attacks are converted into attack trees which are used to estimate the overall risk of the system. Consequently, it becomes possible to study improvements while building a more secure architecture. The proposed method is designed to support the conceptual phase of the vehicle’s cyber-physical system. We illustrate the method on a small pedagogical example to show how it is possible to prove its efficiency.

In this thesis, we present a collection of network generation and information diffusion models expressed using a specific formalism called strategic located graph rewriting, as well as a novel network layout algorithm to show the result of information diffusion in large social networks. Graphs are extremely versatile mathematical objects which can be used to represent a wide variety of high-level systems. They can be transformed in multiple ways (e.g., creating new elements, merging or altering existing ones), but such modifications must be controlled to avoid unwanted operations. To ensure this point, we use a specific formalism called strategic graph rewriting. In this work, a graph rewriting system operates on a single graph, which can then be transformed according to some transformation rules and a strategy to steer the transformation process. First, we adapt two social network generation algorithms in order to create new networks presenting small-world characteristics. Then, we translate different diffusion models to simulate information diffusion phenomena. By adapting the different models into a common formalism, we make their comparison much easier along with the adjustment of their parameters. Finally, we finish by presenting a novel compact layout method to display overviews of the results of our information diffusion method., Dans cette thèse, nous présentons à la fois une collection de modèles de générations de réseaux et de diffusion d'information exprimés à l'aide d'un formalisme particulier appelé la réécriture de graphes, ainsi qu'une nouvelle méthode de représentation permettant la visualisation de la diffusion d'information dans des grands réseaux sociaux. Les graphes sont des objets mathématiques particulièrement versatiles qui peuvent être utilisés pour représenter une large variété de systèmes abstraits. Ces derniers peuvent être transformés de multiples façons (création, fusion ou altération de leur éléments), mais de telles modifications doivent être contrôlées afin d'éviter toute opération non souhaitée. Pour cela, nous faisons appel au formalisme particulier de la réécriture de graphes afin d'encadrer et de contrôler toutes les transformations. Dans notre travail, un système de réécriture de graphes opère sur un graphe, qui peut être transformé suivant un ensemble de règles, le tout piloté par une stratégie. Nous commençons tout d'abord par utiliser la réécriture en adaptant deux algorithmes de génération de réseaux, ces derniers permettant la création de réseaux aux caractéristiques petit monde. Nous traduisons ensuite vers le formalisme de réécriture différents modèles de diffusion d'information dans les réseaux sociaux. En énonçant à l'aide d'un formalisme commun différents algorithmes, nous pouvons plus facilement les comparer, ou ajuster leurs paramètres. Finalement, nous concluons par la présentation d'un nouvel algorithme de dessin compact de grands réseaux sociaux pour illustrer nos méthodes de propagation d'information.

This article studies the snow plow routing problem, which is a modified version of the min–max problem with k-vehicles for arc routing on a mixed graph with hierarchy. Each arc or edge is given a priority and instead of minimizing the overall finishing time, we minimize the latest finishing time for each priority class. We consider turn restrictions, route balancing, and variable vehicle speeds in a real large-scale network. To solve the problem, we present a graph transformation from a directed rural postman problem with turn penalties to an asymmetric traveling salesman problem. We then make the following modifications to the metaheuristics to better handle the constraints: development of new neighborhood operators, several applications of the same destruction operators before repair of the solution, and a dynamic arc-grouping procedure when links are removed or inserted. We tested our methodology on three real networks with 1,626 to 2,146 street segments and 613 to 723 intersections. The results show that our approach can improve the solution, and the grouping procedure is helpful. The results also show that some operators perform better than others; the network topology seems to explain these variations. Finally, we validated our methodology by comparing to some routes planned in the past and to some routes obtained from a commercial solver. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 195–215 2017

International audience; We present a general definition of labelled port graph that serves as a basis for the design of graph-based programming and modelling frameworks (syntax and semantics). We show that this structure provides the syntax for programs, which are composed of an initial graph, a set of rules and a strategy. Rules, represented as labelled port graphs, apply to states, also represented as labelled port graphs, and compute their successors according to the given strategy. The description of states, rules, and computations controlled by strategies, using labelled port graphs, is detailed and illustrated with examples from Porgy, a strategic port graph rewriting environment for the design of executable specifications of complex systems.

We present attributed hierarchical port graphs (AHP) as an extension of port graphs that aims at facilitating the design of modular port graph models for complex systems. AHP consist of a number of interconnected layers, where each layer defines a port graph whose nodes may link to layers further down the hierarchy; attributes are used to store user-defined data as well as visualisation and run-time system parameters. We also generalise the notion of strategic port graph rewriting (a particular kind of graph transformation system, where port graph rewriting rules are controlled by user-defined strategies) to deal with AHP following the Single Push-out approach. We outline examples of application in two areas: functional programming and financial modelling., In Proceedings WPTE 2017, arXiv:1802.05862

In the context of topology-based geometric modeling, operations transform objects regarding both their topological structure (i.e. cell subdivision: vertex, edge, face, etc.) and their embeddings (i.e. relevant data: vertex positions, face colors, volume densities, etc.). Graph transformations with variables allow us to generically handle those operations. We use two types of variables: orbit variables to abstract topological cells and node variables to abstract embedding data. We show how these variables can be simultaneously used, and we provide syntactic conditions on rules to ensure that they preserve object consistency. This rule-based approach is the cornerstone of Jerboa, a tool that allows a fast and safe prototyping of geometric modelers.

International audience; Some recent algebraic approaches to graph transformation include a pullback construction involving the match, that allows one to specify the cloning of items of the host graph. We pursue further this trend by proposing the Pullback-Pushout (pb-po) Approach, where we combine smoothly the classical modifications to a host graph specified by a rule (a span of graph morphisms) with the cloning of structures specified by another rule. The approach is shown to be a conservative extension of agree (and thus of the sqpo approach), and we show that it can be extended with standard techniques to attributed graphs. We discuss conditions to ensure a form of locality of transformations, and conditions to ensure that the attribution of transformed graphs is total.

International audience; We examine the problem of quality awareness when querying graph databases. According to quality annotations that denote quality problems appearing in data subgraphs (the annotations typically result from collaborative practices in the context of open data usage like e.g. users’ feedbacks), we propose a notion of quality aware (graph pattern) query based on (usage-dependent) quality profiles. In this paper, we present the formal foundations of the approach. We also show how to simply extend a generic state-of-the-art algorithm for graph pattern queries evaluation in order to implement quality awareness at evaluation time and we study its complexity. We then expose implementation guidelines, supported by a proof-of-concept prototype based on the Neo4J graph database management system.

Mes recherches récentes portent sur le développement de techniques et outils pour la modélisation de systèmes complexes ; en particulier, des voies de signalisation dans les cellules qui sont notamment impliquées, en cas de dérèglement, dans de nombreuses maladies. Ces travaux, en collaboration avec des collègues en France et aux États-unis, couvrent un spectre assez large, allant des travaux fondamentaux plutôt d’ordre mathématique à la production de code pour en construire des vrais outils de modélisation et d’analyse de modèles. Mes travaux les plus récents intègrent des notions de représentation de connaissances et ontologies sémantiques pour améliorer et simplifier le processus de production de modèles avec le but ultime d’automatiser ce processus le plus possible ; ce travail se fait dans le cadre de deux projets DARPA (‘Big Mechanism’ et ‘Communicating with Computers’).Ces derniers travaux m’ont amené vers un nouveau projet qui consiste à formaliser la notion de méta-modélisation en générale et de faire un développement détaillé d’un cas particulier de ce cadre pour la bio-curation. En effet, de nos jours, la production de modèles en biologie moléculaire est surtout limitée par la difficulté à recolter et combiner toutes les connaissances nécessaires qui se trouvent dispersées dans une littérature vaste et peu structurée. Mon projet propose un cadre théorique et un développement logiciel qui permet d’agréger les connaissances et structurer les hypothèses (souvent en conflit) pour permettre une analyse de leurs conséquences et ainsi la reconciliation progressive des conflits apparents.

Graph rewriting formalisms are well-established models for the representation of biological systems such as protein-protein interaction networks. The combinatorial complexity of these models usually prevents any explicit representation of the variables of the system, and one has to rely on stochastic simulations in order to sample the possible trajectories of the underlying Markov chain. The bottleneck of stochastic simulation algorithms is the update of the propensity function that describes the probability that a given rule is to be applied next. In this paper we present an algorithm based on a data structure, called extension basis, that can be used to update the counts of predefined graph observables after a rule of the model has been applied. Extension basis are obtained by static analysis of the graph rewriting rule set. It is derived from the construction of a qualitative domain for graphs and the correctness of the procedure is proven using a purely domain theoretic argument.

Analysing and reasoning on model transformations has become very relevant for various applications such as ensuring the correctness of transformations. ATL is a model transformation language with rich semantics and a focus on usability, making its analysis not straightforward. Conversely, algebraic graph transformation (AGT) is an approach with strong theoretical foundations allowing for formal analyses that would be valuable in the context of ATL. In this paper, we propose a translation of ATL to the AGT framework in the objective of bringing theoretical analyses of AGT to ATL transformations. We show that this transformation supports a sufficient subset of ATL to be used on an industrial application example: QGen, a qualifiable Simulink $$^{\circledR }$$ to source code generator developed at AdaCore. In addition to this example, we validate our proposal by translating a set of feature-rich ATL transformations to the Henshin AGT framework. We execute the ATL and AGT versions on the same set of models and verify that the result is the same.

Consider a graph having quantum systems lying at each node. Suppose that the whole thing evolves in discrete time steps, according to a global, unitary causal operator. By causal we mean that information can only propagate at a bounded speed, with respect to the distance given by the graph. Suppose, moreover, that the graph itself is subject to the evolution, and may be driven to be in a quantum superposition of graphs---in accordance to the superposition principle. We show that these unitary causal operators must decompose as a finite-depth circuit of local unitary gates. This unifies a result on Quantum Cellular Automata with another on Reversible Causal Graph Dynamics. Along the way we formalize a notion of causality which is valid in the context of quantum superpositions of time-varying graphs, and has a number of good properties. Keywords: Quantum Lattice Gas Automata, Block-representation, Curtis-Hedlund-Lyndon, No-signalling, Localizability, Quantum Gravity, Quantum Graphity, Causal Dynamical Triangulations, Spin Networks, Dynamical networks, Graph Rewriting., 8 pages, 1 figure

Mes recherches récentes portent sur le développement de techniques et outils pour la modélisation de systèmes complexes ; en particulier, des voies de signalisation dans les cellules qui sont notamment impliquées, en cas de dérèglement, dans de nombreuses maladies. Ces travaux, en collaboration avec des collègues en France et aux États-unis, couvrent un spectre assez large, allant des travaux fondamentaux plutôt d’ordre mathématique à la production de code pour en construire des vrais outils de modélisation et d’analyse de modèles. Mes travaux les plus récents intègrent des notions de représentation de connaissances et ontologies sémantiques pour améliorer et simplifier le processus de production de modèles avec le but ultime d’automatiser ce processus le plus possible ; ce travail se fait dans le cadre de deux projets DARPA (‘Big Mechanism’ et ‘Communicating with Computers’).Ces derniers travaux m’ont amené vers un nouveau projet qui consiste à formaliser la notion de méta-modélisation en générale et de faire un développement détaillé d’un cas particulier de ce cadre pour la bio-curation. En effet, de nos jours, la production de modèles en biologie moléculaire est surtout limitée par la difficulté à recolter et combiner toutes les connaissances nécessaires qui se trouvent dispersées dans une littérature vaste et peu structurée. Mon projet propose un cadre théorique et un développement logiciel qui permet d’agréger les connaissances et structurer les hypothèses (souvent en conflit) pour permettre une analyse de leurs conséquences et ainsi la reconciliation progressive des conflits apparents.

International audience; In the last years, ontology modeling became popular and thousands of ontologies covering multiple fields of application are now available. However, as multiple ontologies might be available on the same or related domain, there is an urgent need for tools to compare, match, merge and assess ontologies. Ontology matching, which consists in aligning ontology, has been widely studied and benchmarks exist to evaluate the different matching methods. However, somewhat surprisingly, there are no significant benchmarks for merging ontologies, proving input ontologies and the resulting merged ontology. To fill this gap, we propose a benchmark for ontologies merging, which contains different ontologies types, for instance: taxonomies, lightweight ontologies, heavyweight ontologies and multilingual ontologies. We also show how the GROM tool (Graph Rewriting for Ontology Merging) can address the merging process and we evaluate it based on coverage, redundancy and coherence metrics. We performed experiments and show that the tool obtained good results in terms of redundancy and coherence.

International audience; Parallel independence between transformation steps is a basic notion in the algebraic approaches to graph transformation, which is at the core of some static analysis techniques like Critical Pair Analysis. We propose a new categorical condition of parallel independence and show its equivalence with two other conditions proposed in the literature, for both left-linear and non-left-linear rules. Next we present some preliminary experimental results aimed at comparing the three conditions with respect to computational efficiency. To this aim, we implemented the three conditions, for left-linear rules only, in the Verigraph system, and used them to check parallel independence of pairs of overlapping redexes generated from some sample graph transformation systems over categories of typed graphs.

The use of Complex Event Processing (CEP) and Stream Processing (SP) systems to process high-volume, high-velocity Big Data has renewed interest in procedures for managing these systems. In particular, self-management and adaptation of runtime platforms have been common research themes, as most of these systems run under dynamic conditions. Nevertheless, the research landscape in this area is still young and fragmented. Most research is performed in the context of specific systems, and it is difficult to generalize the results obtained to other contexts. To enable generic and reusable CEP/SP system management procedures and self-management policies, this research introduces the Attributed Graph Rewriting for Complex Event Processing Management ( AGeCEP ) formalism. AGeCEP represents queries in a language- and technology-agnostic fashion using attributed graphs. Query reconfiguration capabilities are expressed through standardized attributes, which are defined based on a novel classification of CEP query operators. By leveraging this representation, AGeCEP also proposes graph rewriting rules to define consistent reconfigurations of queries. To demonstrate AGeCEP feasibility, this research has used it to design an autonomic manager and to define a selected set of self-management policies. Finally, experiments demonstrate that AGeCEP can indeed be used to develop algorithms that can be integrated into diverse CEP systems.