Graph Transformations

ISBN-13: 9783540874041 / Angielski / Miękka / 2008 / 542 str.

Hartmut Ehrig

Opis

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

Spis treści

Invited Papers.- Towards an Algebraic Theory of Bidirectional Transformations.- Discovery, Verification and Conformance of Workflows with Cancellation.- The AUTOSAR Way of Model-Based Engineering of Automotive Systems.- Hypergraphs and Termgraph Rewriting.- An Algorithm for Hypergraph Completion According to Hyperedge Replacement Grammars.- Labelled (Hyper)Graphs, Negotiations and the Naming Problem.- Abstracting Complex Data Structures by Hyperedge Replacement.- Inductively Sequential Term-Graph Rewrite Systems.- Applications of Graph Transformation.- Mobile Agents Implementing Local Computations in Graphs.- A Decentralized Implementation of Mobile Ambients.- Network Applications of Graph Bisimulation.- Graph Transformation for Topology Modelling.- Execution of Graph Transformations.- Embedding and Confluence of Graph Transformations with Negative Application Conditions.- Formal Analysis of Model Transformations Based on Triple Graph Rules with Kernels.- Semantical Correctness and Completeness of Model Transformations Using Graph and Rule Transformation.- High-Level Programs and Program Conditions.- Compositional Systems.- Parallel and Sequential Independence for Borrowed Contexts.- Behavior Preservation in Model Refactoring Using DPO Transformations with Borrowed Contexts.- Open Petri Nets: Non-deterministic Processes and Compositionality.- Validation and Verification.- Attributed Graph Constraints.- Resolution-Like Theorem Proving for High-Level Conditions.- Towards the Verification of Attributed Graph Transformation Systems.- A Modal-Logic Based Graph Abstraction.- Graph Languages and Special Transformation Concepts.- On the Recognizability of Arrow and Graph Languages.- Graph Multiset Transformation as a Framework for Massively Parallel Computation.- Pullback Grammars Are Context-Free.- On Switching to H-Free Graphs.- Patterns and Model Transformations.- A Benchmark Evaluation of Incremental Pattern Matching in Graph Transformation.- 15 Years of Triple Graph Grammars.- Pattern-Based Model-to-Model Transformation.- Adaptive Star Grammars for Graph Models.- Tutorial and Workshops.- Tutorial Introduction to Graph Transformation.- Workshop on Graph Computation Models.- Graph-Based Tools: The Contest.- Workshop on Petri Nets and Graph Transformations.- Summary of the Workshop on Natural Computing and Graph Transformations.- Doctoral Symposium.- ICGT 2008 Doctoral Symposium.- Verification of Architectural Refactorings: Rule Extraction and Tool Support.- Abstract Semantics by Observable Contexts.- Triple Graph Grammars and OCL for Validating System Behavior.- From Separation Logic to Hyperedge Replacement and Back.- Security, Cryptography and Directed Bigraphs.- Modelling Clustering of Sensor Networks with Synchronised Hyperedge Replacement.- Grammar Morphisms and Weakly Adhesive Categories.- Process Construction and Analysis for Workflows Modelled by Adhesive HLR Systems with Application Conditions.- Towards a Two Layered Verification Approach for Compiled Graph Transformation.- Model-Based Analysis of Network Reconfigurations Using Graph Transformation Systems.- Service Extraction from Legacy Systems.- Development of Correct Graph Transformation Systems.- Graph Transformation for the Semantic Web: Queries and Inference Rules.- Using a Triple Graph Grammar for State Machine Implementations.- Model-Driven Development of Model Transformations.- Transformation-Based Operationalization of Graph Languages.

Blurb

This book constitutes the refereed proceedings of the 4th International Conference on Graph Transformations, ICGT 2008, held in Leicester, UK, in September 2008.

The 27 revised full papers presented together with 5 tutorial and workshop papers and 3 invited lectures were carefully selected from 57 submissions. All current aspects in graph drawing are addressed including hypergraphs and termgraph rewriting, applications of graph transformation, execution of graph transformations, compositional systems, validation and verification, graph languages and special transformation concepts, as well as patterns and model transformations. In addition the volume contains 17 short papers of the ICGT 2008 Doctoral Symposium.