In this paper we solve fundamental graph optimization problems like Maximum Clique and Minimum Coloring with recent advances of Monte-Carlo Search. The optimization problems are implemented as single-agent games in a generic state-space search framework, roughly comparable to what is encoded in PDDL for an action planner.

In this paper, we introduce the notion of a community of autonomous units as a rulebased and graph-transformational device to model processes that run interactively but independently of each other in a common environment. The main components of an autonomous unit are a set of rules, a control condition, and a goal. Every autonomous unit transforms graphs by applying its rules so that the control condition is satisfied. If the goal is reached the resulting transformation process is successful. A community contains a set of autonomous units, an initial environment specification, and an overall goal. In every transformation process of a community the autonomous units interact via their common environment. As an example, the game Ludo is modeled as a community of self-controlled players who interact on a common board. The emphasis of the presented approach is laid on the study of the formal semantics of a community as a whole and of each of its member units separately. In particular, a sequential as well as a parallel semantics is introduced, and communities with parallel semantics are compared with Petri nets, cellular automata, and multiagent systems.

This paper shows how integrated UML models combining class, object, use-case, collaboration and state diagrams can be animated in a domain-specific layout. The presented approach is based on graph transformation, i.e., UML model diagrams are translated to a graph transformation system and the behavior of the integrated model is simulated by applications of graph transformation rules. For model validation, users may prefer to see the behavior of selected model aspects as scenarios presented in the layout of the application domain. We propose to integrate animation views with the model's graph transformation system. A prototypical validation system has been implemented recently supporting the automatic translation of a UML model into a graph transformation system, and the interactive execution and simulation of the model behavior. We sketch the tool interconnection to GenGED, a visual language environment which allows to enrich graph transformation systems for model simulation by features for animation.

In this paper we introduce a new hierarchical graph model to structure large graphs into small components by distributing the nodes (and, likewise, edges) into a hierarchy of packages. In contrast to other known approaches, we do not fix the type of underlying graphs. Moreover, our model is equipped with a rule-based transformation concept such that hierarchical graphs are not restricted to being used only for the static representation of complex system states, but can also be used to describe dynamic system behaviour.

Abstract. The aim of the paper is to introduce the notion of a transformation unit together with its interleaving semantics and to study it as a means of constructing large graph transformation systems from small ones in a structured and systematic way. A transformation unit comprises a set of rules, descriptions of initial and terminal graphs, and a control condition. Moreover, it may import other transformation units for structuring purposes. Its semantics is a binary relation between initial and terminal graphs which is given by interleaving sequences. As a generalization of ordinary derivations, an interleaving sequence consists of direct derivation steps interleaved with calls of imported transformation units. It must obey the control condition and may be seen as a kind of structured derivation. The introduced framework is independent of a particular graph transformation approach and, therefore, it may enhance the usefulness of graph transformations in many contexts.

In this paper, we introduce a new concept for the structured development of rule-based graph transformation systems that allows to build up large systems from small pieces in a modular way. The concept is called nested graph transformation unit and consists of a network of local graph transformation units. While each local unit provides a set of rules and control conditions (including input and output descriptions), the net reflects the import structure of the system where each local unit can use its direct neighbours without any restrictions. In particular, the import structure may contain cycles. It is shown that nested graph transformation units have a reasonable operational semantics by iterating the so-called interleaving operator, which interleaves local rule applications with calls of used units according to the local control conditions. It turns out that the iterated interleaving semantics is the smallest fixed point of the interleaving operator provided that the involved control conditions are continuous in a certain sense.