Wyniki wyszukiwania - Biblioteka Nauki

1

Lazy Graph Transformation

100%

Orejas F. , Lambers L.

|

2012

|

tom Vol. 118, nr 1-2

65-96

EN

Applying an attributed graph transformation rule to a given object graph always implies some kind of constraint solving. In many cases, the given constraints are almost trivial to solve. For instance, this is the case when a rule describes a transformation G ⇒ H, where the attributes of H are obtained by some simple computation from the attributes of G. However there are many other cases where the constraints to solve may be not so trivial and, moreover, may have several answers. This is the case, for instance, when the transformation process includes some kind of searching. In the current approaches to attributed graph transformation these constraints must be completely solved when defining the matching of the given transformation rule. This kind of early binding is well-known from other areas of Computer Science to be inadequate. For instance, the solution chosen for the constraints associated to a given transformation step may be not fully adequate, meaning that later, in the search for a better solution, we may need to backtrack this transformation step. In this paper, based on our previous work on the use of symbolic graphs to deal with different aspects related with attributed graphs, including attributed graph transformation, we present a new approach that, based on the new notion of narrowing graph transformation rule, allows us to delay constraint solving when doing attributed graph transformation, in a way that resembles lazy computation. For this reason, we have called lazy this new kind of transformation. Moreover, we show that the approach is sound and complete with respect to standard attributed graph transformation. A running example, where a graph transformation system describes some basic operations of a travel agency, shows the practical interest of the approach.

2

M-Adhesive Transformation Systems with Nested Application Conditions. Part 2: Embedding, Critical Pairs and Local Confluence

71%

Ehrig H. , Golas U. , Habel A. , Lambers L. , Orejas F.

|

2012

|

tom Vol. 118, nr 1-2

35-63

EN

Graph transformation systems have been studied extensively and applied to several areas of computer science like formal language theory, the modeling of databases, concurrent or distributed systems, and visual, logical, and functional programming. In most kinds of applications it is necessary to have the possibility of restricting the applicability of rules. This is usually done by means of application conditions. In this paper, we continue the work of extending the fundamental theory of graph transformation to the case where rules may use arbitrary (nested) application conditions. More precisely, we generalize the Embedding theorem, and we study how local confluence can be checked in this context. In particular, we define a new notion of critical pair which allows us to formulate and prove a Local Confluence Theorem for the general case of rules with nested application conditions. All our results are presented, not for a specific class of graphs, but for any arbitraryM-adhesive category, which means that our results apply to most kinds of graphical structures. We demonstrate our theory on the modeling of an elevator control by a typed graph transformation system with positive and negative application conditions.

3

A Generic Approach to Connector Architectures. Part II: Instantiation to Petri Nets and CSP

61%

Orejas F. , Klein M. , Pino E. , Ehrig H. , Padberg J. , Pérez S.

|

2010

|

tom Vol. 99, nr 1

95-124

EN

The aim of this paper is to show how the generic approach to connector architectures, presented in the first part of this work, can be applied to a given modeling formalism to define architectural component and connector notions associated to that formalism. Starting with a review of the generic approach, in this second part of the paper we consider two modeling formalisms: elementary Petri nets and CSP. As main results we show that both cases satisfy the axioms of our component framework, so that the results concerning the semantics of architectures can be applied. Moreover, a small case study in terms of Petri Nets is presented in order to show how the results can be applied to a connector architecture based on Petri nets.

4

A Generic Approach to Connector Architectures. Part I: The General Framework

61%

Orejas F. , Klein M. , Pino E. , Ehrig H. , Padberg J. , Pérez S.

|

2010

|

tom Vol. 99, nr 1

63-93

EN

The aim of this paper is to present a generic framework for the modelling of componentbased systems using architectural connectors. More precisely, concepts of component, connector and architecture are presented in a formal generic way, which are independent of any semi-formal or formal modelling approach. The idea is that one could use this framework to define component and connector notions for every given modelling formalism. As a main result, we define the semantics of architectures using graph transformation, showing that the semantics is independent of the order in which the connections are computed, and that the semantics is compatible with transformation. In the continuation of this paper, we show the applicability of our ideas. In particular, our framework is instantiated by Petri nets and CSP, including a case study using Petri Nets.