University of Bremen Logo  
 
Graph Transformation Group
 
Welcome to the Graph Transformation Group (formerly Theoretical Computer Science) in the Department of Mathematics and Computer Science at the University of Bremen, Germany. The group belongs to the Technologie-Zentrum Informatik und Informationstechnik TZI [Centre for Computing and Communication Technologies] and of the interdisciplinary Bremen Research Cluster for Dynamics in Logistics LogDynamics.

Our research concentrates on graph transformation and other rule-based formalisms. Besides the mathematical foundation of the considered approaches, we investigate the relations to application areas including logistics, DNA computing, reversible circuits. Moreover, a smaller part of our work is devoted to various topics of Computer and Society.

TEAM


Prof. Dr Hans-Jörg Kreowski, kreo@informatik.uni-bremen.de
full professor (emeritus)

Dr Berthold Hoffmann, hof@uni-bremen.de
senior lecturer (retired)

Dr Sabine Kuske, kuske@uni-bremen.de
lecturer and research assistant

Wolfgang Krieger wkrieger@uni-bremen.de
Ph.D. student

Aaron Lye, lye@informatik.uni-bremen.de
Ph.D. student, scholarship with the Rosa-Luxemburg-Stiftung

Aljoscha Windhorst windhorst@uni-bremen.de
Ph.D. student



PUBLICATIONS

Publications


RESEARCH

Research of the Graph Transformation group concentrates on graph transformation and other rule-based formalisms. Besides the mathematical foundation of the considered approaches, we investigate the relations to application areas including logistics, DNA computing, reversible circuits. Moreover, a smaller part of our work is devoted to various topics of Computer and Society.

Graph transformation

In computer science it is often necessary to handle and to modify complex data representing, for instance, the structure of a software system or the behaviour of a process. In many cases these data can be suitably modelled as graphs. This general fact results in a great need for graph manipulating mechanisms that are powerful and comprehensible at the same time. In the theory of graph transformation such mechanisms are developed and investigated. The work of the group aims at a systematic extension of the theory and its application to different fields of practice. In particular, studies in the following areas are carried out:
  • context-freeness (node, edge, and context-free and contextual hyperedge replacement),
  • graph centered, rule based systems,
  • structuring concepts for graph transformation systems,
  • recognition of graph languages (syntax analysis, pattern recognition) and algorithmic analysis,
  • properties of graph transformation systems,
  • investigation of parallelism, distribution and concurrency,
  • application of graph transformation to logistic processes,
  • application of graph transformation to the unified modeling language UML.
Research in this area is partially supported by the European Union within the Research Training Network SegraVis (Syntactic and Semantic Integration of Visual Modelling Techniques) since October 2002 and by the Deutsche Forschungsgemeinschaft within the project Abstrakte Implementierung von und Dokumentation mit UML [abstract implementation of and documentation with UML] since January 2000 and the Collaborative Research Centre 637 Autonomous Cooperating Logistic Processes - A Paradigm Shift and its Limitations since January 2004 .

Syntactic methods of picture generation

The study of syntactic methods of picture generation aims at using concepts and results from formal language and automata theory for picture generation. Besides the investigation of classical approaches like chain-code picture languages, L-systems with turtle geometry, cellular automata, array grammars, etc., especially collage grammars are studied. Typical subjects are:

  • collage grammars beyond context-freeness,
  • comparison with classical approaches (see above),
  • tree-oriented representation of picture-generating devices.

These purely theoretical studies are accompanied by the development of systems that allow the evaluation and visualisation of collage grammars. The latest system in this line is COLLAGE-VR, which allows to define multi-coloured context-sensitive collage grammars in two as well as in three dimensions. The derived collages can be saved as PostScript files for inclusion in TeX documents, and they can be displayed. Three-dimensional collages are displayed using a standard VRML viewer. Moreover, the TREEBAG system provides a tree-based environment for picture generation using chain-code, collage, and turtle algebras.

If your browser has the shockwave flash plugin installed you may have a look at the following animations:

The latest examples of generated 3D scenes can be found here!
Or you may have a look at the short but illustrative generated movie by Caroline Diana von Totth (3D Show/8.5 MB/low resolution version).

Algebraic specification

For all stages of software development, beginning with the requirements definition and ending with a running program, specification techniques are defined formally with respect to both syntax and semantics. The major emphasis is laid on:
  • methods that allow for correctness proofs and a modular structure of software systems on all levels of abstraction, and
  • formal tools that provide a systematic way to transform one level of abstraction into the next.

The most important subjects are:

  • partial specification,
  • specification of parameterized data types and parameter passing,
  • algebraic implementation of abstract data types,
  • term rewriting and operational semantics,
  • institutions, logics, and parchments as a meta-theory for specification methods allowing comparison and translation between different frameworks.

Research in this area contributes partly to CoFI (Common Framework Initiative for Algebraic Specification) within the IFIP Working Group 1.3. The goal of CoFI is to get a common agreement in the algebraic specification community about basic concepts, and to provide a family of specification languages at different levels, a development methodology, and tool support.

Computer and society

Projects

The working group was involved in the following projects funded by third parties:

Events

2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005

Mail Address
University of Bremen
Dept. for Math. &
Computer Science

P.O. Box 330 440
28334 Bremen
Germany

Physical Address
Bibliothekstrasse 5
MZH 5130
28359 Bremen

Phone
++49(421)218 64451