In this paper, we investigate the relationship between two elementary operations on derivations in the framework of graph transformation based on adhesive categories: moving a derivation along a derivation based on parallel and sequential independence on one hand and restriction of a derivation with respect to a monomorphism into the start object on the other hand. Intuitively, a restriction clips off parts of the start object that are never matched by a rule application throughout the derivation on the other hand. As main result, it is shown that moving a derivation preserves its spine being the minimal restriction.

Abstract In this paper, we continue the investigation of graph-based reaction systems. We extend the notion by input and output states as well as admitted context sequences to model explicitly input–output relations and decision problems on the inputs. Moreover, we combine extended graph-based reaction systems into families to cover infinite input–output relations and decision problems on infinite sets of graphs. This is used to model NP-problems on graphs and reductions between them as well as to prove their correctness.

In the literature, one encounters the intensely studied classical set-based reaction systems and the more recently introduced generalization to graph-based reaction systems where the considered graphs are directed, simple, and edge-labeled. In this paper, we propose a categorical approach to reaction systems so that a wider spectrum of data structures becomes available on which reaction systems can be based including various types of graphs and of graph-like structures like unlabeled graphs, vertex-labeled graphs, bipartite graphs, and a variety of types of hypergraphs. But also algebraic structures like monoids fit into the framework.

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.

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.

In this paper, we introduce the notions of context-sensitive and ET0L collage grammars as generalizations of context-free collage grammars. Both kinds of picture-generating devices are more,powerful than the context-free case. Nevertheless, the size of collages in an ET0L collage language can be shown to grow at most exponentially. In contrast to this, there are no such bounds for context-sensitive collage languages because suitable pictorial representations of recursively enumerable sets of strings can be generated. On the other hand, it is still a conjecture that ET0L collage languages exist that are not context-sensitive.

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.

Collage grammars are based on hyperedge replacement in a geometric environment and provide context-free syntactic devices for the generation of picture languages. An intriguing question is which geometric properties of the generated pictures can be decided by inspecting the generating collage grammars. The results presented in this paper address the question in two respects. (1) The decidability results known for hyperedge replacement grammars generating graph languages, based on the notion of compatibility, can be carried over to collage grammars. Unfortunately, compatible properties seem rare in the geometric setting. In this paper three concrete ones are presented. (2) In some other cases being only a minor extensions of situations for which compatibility is obtained, we can prove undecidability results.

In this paper, we investigate several logical frameworks whose expressiveness lies between Conditional Equational Logic and Horn Clause Logic. The main result deals with thePART-construction, which interprets total based algebras as partial algebras. This construction can be viewed as a simulation of Horn Clause Theories by means of Conditional Equational Theories. Other constructions in other frameworks are extendable to simulations in a similar way. The notion of categorical retractive simulation captures some essential properties of these, which allows us to measure the equivalence and difference between institutions.

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.