$\mathcal{M}$ -adhesive categories provide an abstract framework for a large variety of specification frameworks for modelling distributed and concurrent systems. They extend the well-known frameworks of adhesive and weak adhesive HLR categories and integrate high-level constructs such as attribution as in the case of typed attributed graphs. In the current paper, we investigate $\mathcal{M}$ -adhesive transformation systems including negative application conditions (NACs) for transformation rules, which are often used in applications. For such systems, we propose an original equivalence on transformation sequences, calledpermutation equivalence, that is coarser than the classical switch equivalence. We also present a general construction of deterministic processes for $\mathcal{M}$ -adhesive transformation systems based on subobject transformation systems. As a main result, we show that the process obtained from a transformation sequence identifies its equivalence class of permutation-equivalent transformation sequences. Moreover, we show how the analysis of this process can be reduced to the analysis of the reachability graph of a generated Place/Transition Petri net. This net encodes the dependencies between rule applications of the transformation sequence, including the inhibiting effects of the NACs.

Triple graph grammars (TGGs) are a well-established concept for the specification and execution of bidirectional model transformations within model driven software engineering. Their main advantage is an automatic generation of operational rules for forward and backward model transformations, which simplifies specification and enhances usability as well as consistency. In this paper we present several important results for analysing model transformations based on the formal categorical foundation of TGGs within the framework of attributed graph transformation systems. Our first main result shows that the crucial properties of correctness and completeness are ensured for model transformations. In order to analyse functional behaviour, we generate a new kind of operational rule, called aforward translation rule. We apply existing results for the analysis of local confluence for attributed graph transformation systems. As additional main results, we provide sufficient criteria for the verification of functional behaviour as well as a necessary and sufficient condition for strong functional behaviour. In fact, these conditions imply polynomial complexity for the execution of the model transformation. We also analyse information and complete information preservation of model transformations, that is, whether a source model can be reconstructed (uniquely) from the target model computed by the model transformation. We illustrate the results for the well-known model transformation example from class diagrams to relational database models.

Nested application conditions generalise the well-known negative application conditions and are important for several application domains. In this paper, we present Local Church–Rosser, Parallelism, Concurrency and Amalgamation Theorems for rules with nested application conditions in the framework of $\mathcal{M}$ -adhesive categories, where $\mathcal{M}$ -adhesive categories are slightly more general than weak adhesive high-level replacement categories. Most of the proofs are based on the corresponding statements for rules without application conditions and two shift lemmas stating that nested application conditions can be shifted over morphisms and rules.

Finitary $\mathcal{M}$ -adhesive categories are $\mathcal{M}$ -adhesive categories with finite objects only, where $\mathcal{M}$ -adhesive categories are a slight generalisation of weak adhesive high-level replacement (HLR) categories. We say an object is finite if it has a finite number of $\mathcal{M}$ -subobjects. In this paper, we show that in finitary $\mathcal{M}$ -adhesive categories we not only have all the well-known HLR properties of weak adhesive HLR categories, which are already valid for $\mathcal{M}$ -adhesive categories, but also all the additional HLR requirements needed to prove classical results including the Local Church-Rosser, Parallelism, Concurrency, Embedding, Extension and Local Confluence Theorems, where the last of these is based on critical pairs. More precisely, we are able to show that finitary $\mathcal{M}$ -adhesive categories have a unique $\mathcal{E}$ - $\mathcal{M}$ factorisation and initial pushouts, and the existence of an $\mathcal{M}$ -initial object implies we also have finite coproducts and a unique $\mathcal{E}$ ′- $\mathcal{M}$ pair factorisation. Moreover, we can show that the finitary restriction of each $\mathcal{M}$ -adhesive category is a finitary $\mathcal{M}$ -adhesive category, and finitarity is preserved under functor and comma category constructions based on $\mathcal{M}$ -adhesive categories. This means that all the classical results are also valid for corresponding finitary $\mathcal{M}$ -adhesive transformation systems including several kinds of finitary graph and Petri net transformation systems. Finally, we discuss how some of the results can be extended to non- $\mathcal{M}$ -adhesive categories.

Amalgamation is a well-known concept for graph transformations that is used to model synchronised parallelism of rules with shared subrules and corresponding transformations. This concept is especially important for an adequate formalisation of the operational semantics of statecharts and other visual modelling languages, where typed attributed graphs are used for multiple rules with nested application conditions. However, the theory of amalgamation for the double-pushout approach has so far only been developed on a set-theoretical basis for pairs of standard graph rules without any application conditions. For this reason, in the current paper we present the theory of amalgamation for $\mathcal{M}$ -adhesive categories, which form a slightly more general framework than (weak) adhesive HLR categories, for a bundle of rules with (nested) application conditions. The two main results are the Complement Rule Theorem, which shows how to construct a minimal complement rule for each subrule, and the Multi-Amalgamation Theorem, which generalises the well-known Parallelism and Amalgamation Theorems to the case of multiple synchronised parallelism. In order to apply the largest amalgamated rule, we use maximal matchings, which are computed according to the actual instance graph. The constructions are illustrated by a small but meaningful running example, while a more complex case study concerning the firing semantics of Petri nets is presented as an introductory example and to provide motivation.

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

Abstract The complexity of large system models in software engineering nowadays is mastered by using different views. View-based modelling aims at creating small, partial models, each one of them describing some aspect of the system. Existing formal techniques supporting view-based visual modelling are based on typed attributed graphs, where views are related by typed attributed graph morphisms. Such morphisms up to now require a meta model given by a fixed type graph, as well as a fixed data signature and domain. This is in general not adequate for view-oriented modeling where only parts of the complete meta model are known and necessary when modelling a partial view of the system. The aim of this paper is to extend the framework of typed attributed graph morphisms to generalized typed attributed graph morphisms, short GAG-morphisms, which involve changes of the type graph, data signature, and domain. This allows the modeller to formulate type hierarchies and views of visual languages defined by GAG-morphisms between type graphs, short GATG-morphisms. In this paper, we study the interaction and integration of views, and the restriction of views along type hierarchies. In the main result, we present suitable conditions for the integration and decomposition of consistent view models (Theorem 4.1) and extend these conditions to view models defined over meta models with constraints (Theorem 5.1). As a running example, we use a visual domain-specific modelling language to model coarse-grained IT components and their connectors in decentralized IT infrastructures. Using constraints, we formulate connection properties as invariants.

Abstract Graph constraints were introduced in the area of graph transformation, in connection with the notion of (negative) application conditions, as a form to limit the applicability of transformation rules. However, we believe that graph constraints may also play a significant role in the area of visual software modelling or in the specification and verification of semi-structured documents or websites (i.e. HTML or XML sets of documents). In this sense, after some discussion on these application areas, we concentrate on the problem of how to prove the consistency of specifications based on this kind of constraints. In particular, we present proof rules for two classes of graph constraints and show that our proof rules are sound and (refutationally) complete for each class. In addition, we study clause subsumption in this context as a form to speed up refutation.

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.

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.

Conventional modeling techniques for communication-based systems like Petri nets or UML are restricted to model communication based on a static, immutable network topology. In our research project "Formal modeling and analysis of flexible processes in mobile ad-hoc networks", we have proposed an appropriate integration of Petri nets and Petri net transformation rules, based on graph transformation, leading to a visual formal modeling technique, called reconfigurable Petri nets. In this paper, we extend this previous work on reconfigurable Petri nets on the one hand by marking-changing Petri net transformations, and on the other hand by a technique parallelizing the application of net transformation rules at several matches at once. Both extensions together allow a flexible modeling of communication concepts in communication spaces, like e.g. multicasting, where one actor transmits contents to a group of selected actors. We apply our extended technique to model multicasting group communication in the Internet telephone system Skype.

We propose a framework for the specification of behaviour-preserving reconfigurations of systems modelled as Petri nets. The framework is based on open nets, a mild generalisation of ordinary Place/Transition nets suited to model open systems which might interact with the surrounding environment and endowed with a colimit-based composition operation. We show that natural notions of bisimilarity over open nets are congruences with respect to the composition operation. The considered behavioural equivalences differ for the choice of the observations, which can be single firings or parallel steps. Additionally, we consider weak forms of such equivalences, arising in the presence of unobservable actions. We also provide an up-to technique for facilitating bisimilarity proofs. The theory is used to identify suitable classes of reconfiguration rules (in the double-pushout approach to rewriting) whose application preserves the observational semantics of the net.

Flexibility and interoperability make web services well suited for designing highly-customizable reactive service-based ap-plications, that is interactive applications that can be rapidly adapted to new requirements and environmental conditions. This is the case, for example of personal data managers that many users tailor to their needs to meet different usage con-ditions and requests. In this paper, we propose a model-based approach that provides users with the ability of rapidly developing, adapt-ing and reconfiguring reactive service-based applications to meet new requirements and needs. Users specify their needs by describing sample executions that include interactions with web services through an intuitive interface. Interac-tions are stored in a visual formalism that integrates live sequence charts with graph transformation systems. Mod-els can be visualized, modified, executed and automatically analyzed to identify inconsistencies.

Motivated by recent work on the derivation of labelled transitions and bisimulation congruences from unlabelled reaction rules, we show how to address this problem in the DPO (double-pushout) approach to graph rewriting. Unlike the case with previous approaches, we consider graphs as objects, rather than arrows, of the category under consideration. This allows us to present a very simple way of deriving labelled transitions (called rewriting steps with borrowed context), which integrates smoothly with the DPO approach, has a very constructive nature and requires only a minimum of category theory. The core part of this paper is the proof that the bisimilarity based on graph rewriting with borrowed contexts is a congruence relation. We will also introduce some proof techniques and compare our approach with the derivation of labelled transitions via relative pushouts.

Several approaches exist to define a visual language (VL). Among those the meta-modeling approach used to define the Unified Modeling Language (UML), and the graph transformation approach are very popular. Especially the combination of both, using meta-modeling to define the syntax of a VL and graph transformation for specifying model transformations has been considered conceptually and explored in a number of applications. A formal integration of both approaches has just been started by integrating classical algebraic graph grammars with a node type inheritance concept. In this paper, the integration of inheritance is extending to attributed graph transformation. More precisely, we define attributed type graphs with inheritance leading to a formal integration of inheritance with typed attributed graph transformation.

In order to model the behaviour of open concurrent systems by means of Petri nets, we introduce open Petri nets, a generalisation of the ordinary model where some places, designated as open, represent an interface between the system and the environment. Besides generalising the token game to reflect this extension, we define a truly concurrent semantics for open nets by extending the Goltz–Reisig process semantics of Petri nets. We introduce a composition operation over open nets, characterised as a pushout in the corresponding category, suitable for modelling both interaction through open places and synchronisation of transitions. The deterministic process semantics is shown to be compositional with respect to such a composition operation. If a net . Technically, our result is similar to the amalgamation theorem for data-types in the framework of algebraic specification. A possible application field of the proposed constructions and results is the modelling of interorganisational workflows, recently studied in the literature. This is illustrated by a running example.

Graph transitions represent an extension of the DPO approach to graph transformation for the specification of reactive systems. In this paper, we develop the theory of concurrency for graph transitions. In particular, we prove a local Church–Rosser theorem and define a notion of shift-equivalence that allows us to represent both intra-concurrency (within the specified subsystem) and inter-concurrency (between subsystem and environment). Via an implementation of transitions in terms of DPO transformations with context rules, a second, more restrictive notion of equivalence is defined that captures, in addition, the extra-concurrency (between operations of the environment). As a running example and motivation, we show how the concepts of this paper provide a formal model for distributed information systems.

The idea of a combined reference model- and view-based specification approach has been proposed recently in the software engineering community. In this paper we present a specification technique based on graph transformations which supports such a development approach. The use of graphs and graph transformations supports an intuitive understanding and an integration of static and dynamic aspects on a well-defined semantical base. On this background, formal notions of view and view relation are developed and the behaviour of views is described by a loose semantics. The integration of two views derived from a common reference model is done in two steps. First, dependencies between the views which are not given by the reference model are determined, and the reference model is extended appropriately. This is the task of a model manager. If the two views and the reference model are consistent, the actual view integration can be performed automatically. For the case of more than two views more general scenarios are developed and discussed. All concepts and results are illustrated at the well-known example of a banking system.

Using a categorical semantics that has been developed recently as a basis, we study composition and refinement as horizontal and vertical structuring techniques for typed graph transformation systems. Composition of graph transformation systems with respect to common subsystems is shown to be compatible with the semantics,i.e., the semantics of the composed system is obtained as the composition of the semantics of the component systems. Moreover, the structure of a composed graph transformation system is preserved during a refinement step in the sense that compatible refinements of the components induce a refinement of the composition. The concepts and results are illustrated by a sample development of a small information system using entity relationship modelling techniques.

In this paper we continue previous work by Sannella, Sokolowski and Tarlecki on parameterization in specification languages. Within the loose approach, we define specification and model level semantics for two kinds of parameterizations (parameterized specifications and specifications of parameterized data types) and describe, in a compositional manner, parameter passing at both levels. Moreover, the specification and the model level semantics of parameter passing are shown to be compatible. We also show that the results obtained do not only apply to the loose approach but can also be directly applicable to the initial framework, and in general to any other kind of monomorphic framework (i.e., a framework where all specifications are monomorphic). In particular, the results obtained generalize and extend previous results for the initial approach. Finally, to obtain our results, new categorical constructions of multiple pushouts, amalgamations and extensions, which generalize standard notions of pushouts, amalgamations and extensions, had to be introduced.

The concept of algebraic high-level net transformation systems combines two important lines of research recently introduced in the literature:algebraic high-level nets(AHL-nets for short) andhigh-level replacement systems(HLR-systems for short). In both cases a categorical formulation of the corresponding theory has turned out to be highly important and is also a good basis for the integration of these concepts in this paper. AHL-nets combine Petri nets with algebraic specifications and provide a powerful specification technique for distributed systems including data types and processes. HLR-systems are transformation systems for high-level structures such as graphs, hypergraphs, algebraic specifications and different kinds of Petri nets. The theory of HLRsystems - formulated already in a categorical framework - is applied in this paper to AHLnets. Thus we obtain AHL-net transformation systems as an instantiation of HLR-systems to AHL-nets. This allows us to build up AHL-nets from basic components and to transform the net structure using rules or productions in the sense of graph grammars. This concept is illustrated by extending the well-known example of ‘dining philosophers’. We are able to show that AHL-net-transformation systems satisfy several important compatibility properties. On the one hand we obtain a local Church-Rosser and Parallelism Theorem, which is well-known for graph grammars and has recently been generalized to HLR-systems. This allows us to analyse concurrency in AHL-nets not only on the token level but also on the level of transformations of the net structure. On the other hand, we consider the ‘fusion’ and ‘union’ constructions for high-level structures, motivated by corresponding concepts for high-level Petri nets in the literature, and we show compatibility of these constructions with derivations of HLR-systems in general and AHL-nettransformations in particular. This means compatibility of vertical and horizontal structuring in terms of software development.

The intention of this part 1 of an overview paper on algebraic specifications is an informal introduction to formal methods for software development in general and to applications of algebraic specifications in particular. Horizontal structuring and vertical refinement techniques for algebraic specifications are shown to support the general software development process. Moreover, a short overview of case studies and tools in the ESPRIT projects LOTOSPHERE and PROSPECTRA is given. In part 2 of this paper we give a survey of the research field of algebraic specifications developed within the last two decades, which shows how the classical view of algebraic specifications has been extended towards a general theory of foundations of system specifications.

Part I of this paper concerning algebraic specifications is an informal introduction to formal methods for software development using algebraic techniques. The intention of this second part of the paper is to survey the research field of algebraic specifications developed within the last two decades and the role of this field concerning formal methods in computer science. The aim of this paper is to show that the classical field of algebraic specifications, using equational axioms, equational logic and algebraic data types and varieties, has reached a consolidated status by now. It can be considered as an important kernel of a more general theory which is presently under development, focusing on the foundations of system specifications in general.

High-level replacement systems are formulated in an axiomatic algebraic framework based on categories pushouts. This approach generalizes the well-known algebraic approach to graph grammars and several other types of replacement systems, especially the replacement of algebraic specifications which was recently introduced for a rule-based approach to modular system design. in this paper basic notions like productions, derivations, parellel and sequential independence are introduced for high-level replacement syetms leading to Church-Rosser, Parallelism and concurrency Theorems previously shown in the literature for special cases only. In the general case of high-level replacement systems specific conditions, called HLR1- and HLR2-conditions, are formulated in order to obtain these results. Several examples of high-level replacement systems are discussed and classified w.r.t. HLR1- and HLR2-conditions showing which of the results are valid in each case.

A modularity concept for structuring large software systems is presented. The concept enforces an extreme modularity discipline that goes considerably beyond the one found in modern programming languages such as MODULA-2 or Ada. The concept is meant to be used to tightly control side effects in the execution of systems that are constructed of independently developed modules. A family of specification languages is introduced whose members are all based on the modularity concept and thus support the uniform monolinguistic specification of software systems at all development stages. The languages have been defined to enable matching informal, semiformal, and formal specifications and thus to make formal specification of modular systems practicable. The construction of large software systems as interconnections of modules is shown to lead to manageable system structures and to new degrees of freedom in the structuring of the software development process. The suitability of the modularity concept has been evaluated in a large software project for the development of a database management system. The concept and specification languages are explained with the aid of sample specifications.

The aim of this paper is to study implementations of abstract data types and their complexity within the framework of algebraic specifications. An implementation of an abstract data type ADTO by an abstract data type ADT1 is defined on a syntactical and on a semantical level where data and operations of ADTO are simulated by those of ADT1. In order to investigate complexity of implemented operations and to compair different implementations we axiomatically introduce complexity measures for the operations in ADTO with respect to a given implementation of ADTO by ADT1. A most natural interesting class of complexity measures which satisfy our axioms is compatible with time complexity of Turing Machines. This is shown by specification and implementation of timebounded Turing Machines within our algebraic framework and the simulation of a general nondeterministic interpreter for algebraic implementations by a nondeterministic Turing Machine. This relationship allows to show the existence of solutions and of upper and lower bounds for the complexity of a broad class of implementation problems in our sense. A corollary shows that there are algebraic specifications for all those recursive functions which are bounded in time by algebraically specifyable functions.

We propose a mathematical foundation for reasoning about the correctness and computational complexity of record handling algorithms, using algebraic methods recently introduced in graph theory. A class of pattern matching and replacement rules for graphs is specified, such that applications of rules in the class can readily be programmed as rapid transformations of record structures. When transformations of record structures are formalized as applications of rules to appropriate graphs, recent Church–Rosser type theorems of algebraic graph theory become available for proving that families of transformations are well behaved. In particular, we show that any Church–Rosser family of transformations can be combined with housekeeping operations involving indirect pointers and garbage collection without losing the Church–Rosser property, provided certain mild conditions on the rules defining the family are satisfied. This leads to suggestions for the design of record handling facilities in high level languages, especially when housekeeping chores are to be performed asynchronously by service processes that run in parallel with the main process. These results and the general theorems that support them can be used to analyze the behavior of a large record structure that can be updated asynchronously by several parallel processes or users.