Wyniki wyszukiwania - BazTech

1

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

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

Fundamenta Informaticae

|

2012

|

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.

2

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

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

Fundamenta Informaticae

|

2010

|

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.

3

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

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

Fundamenta Informaticae

|

2010

|

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.

4

Theory of Constraints and Application Conditions: From Graphs to High-Level Structures

Ehrig H., Ehrig K., Habel A., Pennemann K-H.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 1

135-166

EN

Graph constraints and application conditions are most important for graph grammars and transformation systems in a large variety of application areas. Although different approaches have been presented in the literature already there is no adequate theory up to now which can be applied to different kinds of graphs and high-level structures. In this paper, we introduce a general notion of graph constraints and application conditions and show under what conditions the basic results can be extended from graph transformation to high-level replacement systems. In fact, we use the new framework of adhesive HLR categories recently introduced as combination of HLR systems and adhesive categories. Our main results are the transformation of graph constraints into right application conditions and the transformation from right to left application conditions in this new framework. The transformations are illustrated by a railroad control system with rail net constraints and application conditions.

5

Fundamental Theory for Typed Attributed Graphs and Graph Transformation based on Adhesive HLR Categories

Ehrig H., Ehrig K., Prange U., Taentzer G.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 1

31-61

EN

The concept of typed attributed graphs and graph transformation is most significant for modeling and meta modeling in software engineering and visual languages, but up to now there is no adequate theory for this important branch of graph transformation. In this article we give a new formalization of typed attributed graphs, which allows node and edge attribution. The first main result shows that the corresponding category is isomorphic to the category of algebras over a specific kind of attributed graph structure signature. This allows to prove the second main result showing that the category of typed attributed graphs is an instance of ''adhesive HLR categories''. This new concept combines adhesive categories introduced by Lack and Soboci\'nski with the well-known approach of high-level replacement (HLR) systems using a new simplified version of HLR conditions. As a consequence we obtain a rigorous approach to typed attributed graph transformation providing as fundamental results the Local Church-Rosser, Parallelism, Concurrency, Embedding and Extension Theorem and a Local Confluence Theorem known as Critical Pair Lemma in the literature.

6

Adhesive High-Level Replacement Systems: A New Categorical Framework for Graph Transformation

Ehrig H., Padberg J., Prange U.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 1

1-29

EN

Adhesive high-level replacement (HLR) systems are introduced as a new categorical framework for graph transformation in the double pushout (DPO) approach, which combines the well-known concept of HLR systems with the new concept of adhesive categories introduced by Lack and Sobociński. In this paper we show that most of the HLR properties, which had been introduced to generalize some basic results from the category of graphs to high-level structures, are valid already in adhesive HLR categories. This leads to a smooth categorical theory of HLR systems which can be applied to a large variety of graphs and other visual models. As a main new result in a categorical framework we show the Critical Pair Lemma for the local confluence of transformations. Moreover we present a new version of embeddings and extensions for transformations in our framework of adhesive HLR systems.

7

Behaviour and Instantiation of High-Level Petri Net Processes

Ehrig H.

Fundamenta Informaticae

|

2005

|

Vol. 65, nr 3

211--247

EN

Processes for high-level nets N are often defined as processes of the low-level net Flat(N) which is obtained from N via the well-known flattening construction. This low-level notion of processes for high-level nets, however, is not really adequate, because the high-level structure is completely lost. For this reason we have introduced in a previous paper a new notion of high-level net processes for high-level nets which captures the high-level structure. The key notion is a high-level occurrence net K, which generalizes the well-known notion of occurrence nets from low-level to high-level nets. In contrast to the low-level case we consider high-level occurrence nets together with a set of initial markings of the input places. In this paper we show under which conditions the behavior of low-level occurrence nets and processes can be generalized to the high-level case. A key notion is the instantiation L of a high-level occurrence net K, where L is a low-level subnet of the flattening Flat(K) with isomorphic net structures of L and K. One of our main results characterizes under which conditions a high-level occurrence net - and hence a high-level net process - has unique and nonoverlapping instantiations and can be represented by the union of all its instantiations.