Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool environment. Finally the appendix covers the basics of category theory, signatures and algebras. The book addresses both research scientists and graduate students in computer science, mathematics and engineering.

Since the early seventies concepts of specification have become central in the whole area of computer science. Especially algebraic specification techniques for abstract data types and software systems have gained considerable importance in recent years. They have not only played a central role in the theory of data type specification, but meanwhile have had a remarkable influence on programming language design, system architectures, arid software tools and environments. The fundamentals of algebraic specification lay a basis for teaching, research, and development in all those fields of computer science where algebraic techniques are the subject or are used with advantage on a conceptual level. Such a basis, however, we do not regard to be a synopsis of all the different approaches and achievements but rather a consistently developed theory. Such a theory should mainly emphasize elaboration of basic concepts from one point of view and, in a rigorous way, reach the state of the art in the field. We understand fundamentals in this context as: 1. Fundamentals in the sense of a carefully motivated introduction to algebraic specification, which is understandable for computer scientists and mathematicians. 2. Fundamentals in the sense of mathematical theories which are the basis for precise definitions, constructions, results, and correctness proofs. 3. Fundamentals in the sense of concepts from computer science, which are introduced on a conceptual level and formalized in mathematical terms.

The aim of this book is to present fundamentals of algebraic specifications with respect to the following three aspects: fundamentals in the sense of a carefully motivated introduction to algebraic specifications, which is easy to understand for computer scientists and mathematicians; fundamentals in the sense of mathematical theories which are the basis for precise definitions, constructions, results, and correctness proofs; and fundamentals in the sense of concepts, which are introduced on a conceptual level and formalized in mathematical terms. The book is equally suitableas a text book for graduate courses and as a reference for researchers and system developers.

Since the early seventies concepts of specification have become central in the whole area of computer science. Especially algebraic specification techniques for abstract data types and software systems have gained considerable importance in recent years. They have not only played a central role in the theory of data type specification, but meanwhile have had a remarkable influence on programming language design, system architectures, arid software tools and environments. The fundamentals of algebraic specification lay a basis for teaching, research, and development in all those fields of computer science where algebraic techniques are the subject or are used with advantage on a conceptual level. Such a basis, however, we do not regard to be a synopsis of all the different approaches and achievements but rather a consistently developed theory. Such a theory should mainly emphasize elaboration of basic concepts from one point of view and, in a rigorous way, reach the state of the art in the field. We understand fundamentals in this context as: 1. Fundamentals in the sense of a carefully motivated introduction to algebraic specification, which is understandable for computer scientists and mathematicians. 2. Fundamentals in the sense of mathematical theories which are the basis for precise definitions, constructions, results, and correctness proofs. 3. Fundamentals in the sense of concepts from computer science, which are introduced on a conceptual level and formalized in mathematical terms.

Graphs are among the simplest and most universal models for a variety of s- tems, not just in computer science, but throughout engineering and the life sciences. When systems evolve we are interested in the way they change, to p- dict, support, or react to their evolution. Graph transformation combines the idea of graphs as a universal modelling paradigm with a rule-based approach to specify their evolution. The area is concerned with both the theory of graph transformation and their application to a variety of domains. The biannual International Conferences on Graph Transformation aim at bringingtogetherresearchersandpractitionersinterestedin the foundations and applicationsof graphtransformation.The ?fth conference, ICGT 2010, was held at the University of Twente (The Netherlands) in September/October 2010, alongwith severalsatellite events.It continuedthe line ofconferences previously held in Barcelona (Spain) in 2002, Rome (Italy) 2004, Natal (Brazil) in 2006 and Leicester (UK) in 2008, as well as a series of six International Workshops on Graph Transformation with Applications in Computer Science from 1978 to 1998. Also, ICGT alternates with the workshop series on Application of Graph Transformation with Industrial Relevance (AGTIVE). The conference was held under the auspices of EATCS and EASS

This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. It contains an introduction to classical graphs. Basic and advanced results are first shown for an abstract form of replacement systems and are then instantiated to several forms of graph and Petri net transformation systems. The book develops typed attributed graph transformation and contains a practical case study.

Graphs are among the simplest and most universal models for a variety of s- tems, not just in computer science, but throughout engineering and the life sciences. When systems evolve we are interested in the way they change, to p- dict, support, or react to their evolution. Graph transformation combines the idea of graphs as a universal modelling paradigm with a rule-based approach to specify their evolution. The area is concerned with both the theory of graph transformation and their application to a variety of domains. The International Conferences on Graph Transformation aim at bringing - getherresearchersandpractitionersinterestedinthefoundationsandapplications of graph transformation. The 4th International Conference on Graph Transf- mation(ICGT2008)washeldinLeicester(UK)inthesecondweekofSeptember 2008, along with severalsatellite events. It continued the line of conferences p- viouslyheld in Barcelona(Spain) in 2002, Rome(Italy) 2004, and Natal(Brazil) in 2006 as well as a series of six International Workshops on Graph Transfor- tion with Applications in Computer Science between 1978 to 1998. Also, ICGT alternateswiththeworkshopseriesonApplicationofGraphTransformationwith Industrial Relevance (AGTIVE). The conference was held under the auspices of EATCS, EASST, andIFIP WG 1.3. Respondingtothecallforpapers,57papersweresubmitted.Thepaperswere reviewedthoroughlybyprogramcommitteemembersandtheirco-reviewers.The committee selected 27 papers for presentation at the conference and publication in the proceedings. These papers mirror well the wide-ranged ongoing research activities in the theory and application of graph transformation. They are c- cerned with di?erent kinds of graph transformation approaches, compositional systems, validation and veri?cation as well as various applications, mainly to model transformation and distributed systems. Paper submission and reviewing were supported by the free conference management system EasyCh

This book constitutes the refereed proceedings of the Third International Conference on Graph Transformations, ICGT 2006. The book presents 28 revised full papers together with 3 invited lectures. All current aspects in graph drawing are addressed including graph theory and graph algorithms, theoretic and semantic aspects, modeling, tool issues and more. Also includes accounts of a tutorial on foundations and applications of graph transformations, and of ICGT Conference satellite events.

This volume is a documentation of the main results in the research area "In- gration of Software Speci?cation Techniques for Applications in Engineering." On one hand it is based on the Priority Program "Integration von Techniken der Softwarespezi?kation fur ] ingenieurwissenschaftliche Anwendungen," short Soft- Spez, oftheGermanResearchCouncil(DFG). Ontheotherhanditcontainsnew contributions of international experts in this research area, some of which were presented at the third international workshop INT 2004 on "Integration of Sp- i?cation Techniques for Applications in Engineering." INT 2004 was launched as a satellite event of ETAPS in Barcelona, the "European Joint Conferences on Theory and Practice of Software." The Priority Program SoftSpez was initiated by W. Brauer, M. Broy, H. Ehrig, H. J. Kreowski, H. Reichel, and H. Weber concerning di?erent aspects from computer science, and by E. Schnieder and E. Westk] amper concerning two main application areas in engineering, namely "Tra?c Control Systems" and "Production Automation." After acceptance of SoftSpez by the German Research Council for the period of 1998-2004 a call for speci?c projects within this priority program was launched, where 11 projects from about 75 project proposals were accepted for a period of two years. Since 1998 each year the main research proposals and results of the projects have been presented at an annual colloquium of the priority program, and every two years the projects have been evaluated by an independent group of referees appointed by the G- man Research Council. At this point we would like to thank A."

ICGT 2004 was the 2nd International Conference on Graph Transformation, following the ?rst one in Barcelona (2002), and a series of six international workshops on graph grammars with applications in computer science between 1978 and 1998. ICGT 2004 was held in Rome (Italy), Sept. 29 Oct. 1, 2004 under the auspices of the European Association for Theoretical Computer S- ence (EATCS), the European Association of Software Science and Technology (EASST), and the IFIP WG 1.3, Foundations of Systems Speci?cation. The scope of the conference concerned graphical structures of various kinds (like graphs, diagrams, visual sentences and others) that are useful when - scribing complex structures and systems in a direct and intuitive way. These structures are often augmented with formalisms that add to the static descr- tion a further dimension, allowing for the modelling of the evolution of systems via all kinds of transformations of such graphical structures. The ?eld of graph transformation is concerned with the theory, applications, and implementation issues of such formalisms. The theory is strongly related to areas such as graph theory and graph - gorithms, formal language and parsing theory, the theory of concurrent and distributed systems, formal speci?cation and veri?cation, logic, and semantics. The application areas include all those ?elds of computer science, information processing, engineering, andthe naturalsciences wherestatic anddynamicm- elling using graphical structures and graph transformations, respectively, play important roles. In many of these areas tools based on graph transformation technology have been implemented and used."

This volume, "Petri Net Technology for Communication-Based Systems," is a state-of-the-artreportin the seriesAdvances in Petri Nets. It showshowvarious well-established and new Petri net notions and techniques can be used for m- elingcommunication-basedsystems, withspecialfocusonwork?owmanagement and business processes. In the last 6 years this topic has been studied by the DFG Forschergruppe Petri Net Technology in Berlin in close cooperation with the international c- munity. The main results of this cooperation were presented at the 1st and 2nd InternationalColloquiaonPetriNetTechnologiesforModelingCommunication- Based Systems, held in Berlin in 1999 and 2001, respectively. A careful selection of contributions by members of the DFG Forschergruppe and by international experts in this ?eld are presented in this volume. Taking into account the fru- ful discussions during the two colloquia and the cross-refereeing process for the accepted papers, a high degree of common understanding was achieved, leading to a highly comprehensive presentation in this volume. The topics of the papers in this volume can be roughly classi?ed into the following two areas: - Petri net technology and - application to communication-based systems. Since most papers comprise aspects of both areas, we chose an alphabetic order. However, in the following we give a rough overview of the contributions in both areas according to the main focus of the corresponding papers.

This book constitutes the refereed proceedings of the First International Conference on Graph Transformations, ICGT 2002, held in Barcelona, Spain in October 2002.The 26 revised full papers presented were carefully reviewed and selected by the program committe. Also included are abstracts of 3 invited papers, a tutorial, the extended abstract of a tutorial, and 5 reports of workshops held in conjunction with ICGT. The papers deal with various graphical structures that are useful to describe complex systems and computational structures, like graphs, diagrams, visual sentences, and others. Graph transformations are stongly related to graph theory, graph algorithms, formal language and parsing theory, the theory of concurrent and distributed systems, formal specification and verification, and logic and semantics.

This book presents state of the art research in theoretical computer science and related ?elds. In particular, the following areas are discussed: automata theory, formal languages and combinatorics of words, graph transformations, Petri nets, concurrency, as well as natural and molecular computing. The articles are written by leading researchers in these areas. The writers were originally invited to contribute to this book but then the normal refereeing procedure was applied as well. All of the articles deal with some issue that has been under vigorous study during recent years. Still, the topics range from very classical ones to issues raised only two or three years ago. Both survey articles and papers attacking speci?c research problems are included. The book highlights some key issues of theoretical computer science, as they seem to us now at the beginning of the new millennium. Being a comprehensive overview of some of the most active current research in theoretical computer science, it should be of de?nite interest for all researchers in the areas covered. The topics range from basic decidability and the notion of information to graph grammars and graph transformations, and from trees and traces to aqueous algorithms, DNA encoding and self-assembly. Special e?ort has been given to lucid presentation. Therefore, the book should be of interest also for advanced students.

Since their introduction nearly 40 years ago, research on Petri nets has diverged in many different directions. Various classes of Petri net, motivated either by theory or applications, with its own specific features and methods of analysis, have been proposed and studies in depth.These successful developments have led to a very heterogeneous landscape of diverse models, and this, in turn, has stimulated research on concepts and approaches that contribute to unifying and structuring the diverse landscape. This state-of-the-art survey presents the most relevant approaches to unifying Petri nets in a systematic and coherent way. The 14 chapters written by leading researchers are organized in topical sections on application-oriented approaches, unifying frameworks, and theoretical approaches.

Theareaofgraphtransformationoriginatedinthelate1960sunderthename "graph grammars" - the main motivation came from practical considerations concerning pattern recognition and compiler construction. Since then, the list of areas which have interacted with the development of graph transformation has grown impressively. The areas include: software speci?cation and development, VLSI layout schemes, database design, modeling of concurrent systems, m- sively parallel computer architectures, logic programming, computer animation, developmentalbiology, musiccomposition, distributedsystems, speci?cationl- guages, software and web engineering, and visual languages. As a matter of fact, graph transformation is now accepted as a fundamental computation paradigm where computation includes speci?cation, programming, and implementation. Over the last three decades the area of graph transfor- tion has developed at a steady pace into a theoretically attractive research ?eld, important for applications. Thisvolume consistsofpapersselectedfromcontributionsto the Sixth Int- national Workshop on Theory and Applications of Graph Transformation that took place in Paderborn, Germany, November 16-20, 1998. The papers und- went an additional refereeing process which yielded 33 papers presented here (out of 55 papers presented at the workshop). This collection of papers provides a very broad snapshot of the state of the art of the whole ?eld today. They are grouped into nine sections representing most active research areas. Theworkshopwasthe sixth in a seriesof internationalworkshopswhich take place every four years. Previous workshops were called "Graph Grammars and Their Application to Computer Science." The new name of the Sixth Workshop re?ectsmoreaccuratelythecurrentsituation, whereboththeoryandapplication play an equally central role.

This book contains a collection of 37 refereed full papers selected from the contributions presented at the 5th International Workshop on Graph Grammars and Their Applications to Computer Science, held in Williamsburg, Virginia, USA, in November 1994.
The book covers the whole spectrum of methods and techniques for the investigation of the structure of graphs and graph transformations. The papers are divided into nine topical sections on rewriting techniques, specification and semantics, software engineering, algorithms and architectures, concurrency, graph languages, pattern and graphics, structure and logic of graphs, and biology.

Research in the area of abstract data types started about 20 years ago. Since then there has been continuous activity with strong influence both on the applications and the theoretical foundations of methodologies for software design. The Ninth Workshop on Specification of Abstract Data Types was held jointly with the Fourth COMPASS Workshop in Spain in 1992.
The main topics covered were: object-oriented specifications, rewriting methods, specification languages and associated tools, type systems, and algebraic specification of concurrency. This volumes contains four invited papers presented at the workshop together with the final versions of 17 contributed papers selected after a careful refereeing process from 46 submissions.

The research area of graph grammars and graph transformations dates back only two decades. But already methods and results from the area of graph transformation have been applied in many fields of computer science, such as formal language theory, pattern recognition and generation, compiler construction, software engineering, concurrent and distributed systems modelling, and database design and theory. This volume contains 24 selected and revised papers from an international seminar held in Dagstuhl, Germany, in 1993. The papers cover topics in the following areas: foundations of graph grammars and transformations; and applications of graph transformations to concurrent computing, specification and programming, and pattern generation and recognition.

This volume contains papers selected from the contributions to the 4th International Workshop on Graph Grammars and Their Application to Computer Science. It is intended to provide a rich source of information on the stateof the art and newest trends to researchers active in the area and for scientists who would like to know more about graph grammars. The topics of the papers range from foundations through algorithmic and implemental aspects to various issues that arise in application areas like concurrent computing, functional and logic programming, software engineering, computer graphics, artificial intelligence and biology. The contributing authors are F.-J. Brandenburg, H. Bunke, T.C. Chen, M. Chytil, B. Courcelle, J. Engelfriet, H. G-ttler, A. Habel, D. Janssens, C. Lautemann, B. Mayoh, U. Montanari, M. Nagl, F. Parisi-Presicci, A. Paz, P. Prusinkiewics, M.R. Sleep, A. Rosenfeld, J. Winkowski and others.

The algebraic specification of abstract data types is now a well establishedresearch topic in computer science. This area influences both applications and theoretical foundations of methodologies which support the design and formal development of reliable software. The Seventh Workshop on Specification of Abstract Data Types took place in Wusterhausen/Dosse, April17-20, 1990, and was organized in cooperation with the ESPRIT Basic Research Working Group COMPASS. The main topics covered by the workshop were: - Modularization - Object orientation - Higher-order types anddependent types - Inductive completion - Algebraic high-level nets.

This volume contains selected papers of the International Workshop on "Categorical Methods in Computer Science - with Aspects from Topology" and of the "6th International Data Type Workshop" held in August/September 1988 in Berlin. The 23 papers of this volume are grouped into three parts: "Part " "1" includes papers on categorical foundations and fundamental concepts from category theory in computer science. "Part 2" presents applications of categorical methods to algebraic specification languages and techniques, data types, data bases, programming, and process specifications. "Part 3" comprises papers on categorial aspects from topology which mainly concentrate on special adjoint situations like cartesian closeness, Galois connections, reflections, and coreflections which are of growing interest in categorical topology and computer science.

The generic term "graph-grammars" refers to a variety of methods for specifying (possibly infinite) sets of graphs or sets of maps. The area of graph-grammars originated in the late 60s motivated by considerations concerning pattern recognition - since then the list of areas which have interacted with the development of graph-grammars has grown quite impressively. It includes pattern recognition, software specification and development, VLSI layout schemes, data bases, lambda-calculus, analysis of concurrent systems, massively parallel computer architectures, incremental compilers, computer animation, complexity theory, developmental biology, music composition, representation of physical solids, and many others. This volume is based on the contributions presented at the third international workshop on graph-grammars and their applications, held in Warrenton, Virginia, USA in December 1986. Aiming at the best possible representation of the field not all of the papers presented at the meeting appear in this volume and some of the papers from this volume were not presented at the workshop. The volume consists of two parts: Part I presents tutorial introductions to a number of basic graph and map rewriting mechanisms. Part II contains technical contributions. This collection of papers provides the reader with an up-to-date overview of current trends in graph-grammars.