Catálogo de publicaciones - libros

Graph grammars are a powerful model of concurrent and distributed systems which can be seen as a proper extension of Petri nets. Inspired by this correspondence, a truly concurrent semantics has been developed along the years for the algebraic approaches to graph grammars, based on Winskel’s style unfolding constructions as well as on suitable notions of processes. A basic role is played in this framework by the study of contextual and inhibitor nets, two extensions of ordinary nets which can be seen as intermediate models between ordinary Petri nets and algebraic graph grammars.

This paper presents a survey of these results, discussing in a precise, even if informal way, some of the main technical contributions that made possible the development of such a theory.

Software engineers usually represent problems and solutions using graph-based notations at different levels of abstractions. These notations are often semi-formal, but the use of graph transformation techniques can support reasoning about graphs in many ways, and thus can largely enhance them.

Recent work indicates many applications of graph transformation to software engineering and opens new research directions. This paper aims primarily at illustrating how graph transformation can help software engineers, but it also discusses how software engineering can ameliorate the practical application of graph transformation technology and its supporting tools.

Modularization is a well-known concept to structure software systems as well as their specifications. Modules are equipped with export and import interfaces and thus can be connected with other modules requesting or providing certain features.

In this paper, we study modules the interfaces of which consist of behavioral specifications given by typed graph transformation systems. We introduce a framework for classifying and systematically defining relations between typed graph transformation systems. The framework comprises a number of standard ingredients, like homomorphisms between type graphs and mappings between sets of graph transformation rules.

The framework is applied to develop a novel concept of substitution morphism by separating preconditions and effects in the specification of rules. This substitution morphism is suited to define the semantic relation between export and import interfaces of requesting and providing modules.

The “classical” approach to represent Petri nets by graph transformation systems is to translate each transition of a specific Petri net to a graph rule (behavior rule). This translation depends on a concrete model and may yield large graph transformation systems as the number of rules depends directly on the number of transitions in the net. Hence, the aim of this paper is to define the behavior of Algebraic High-Level nets, a high-level Petri net variant, by a parallel, typed, attributed graph transformation system. Such a general parallel transformation system for AHL nets replaces the translation of transitions of specific AHL nets. After reviewing the formal definitions of AHL nets and parallel attributed graph transformation, we formalize the classical translation from AHL nets to graph transformation systems and prove the correctness of the translation. The translation approach then is contrasted to a definition for AHL net behavior based on parallel graph transformation. We show that the resulting amalgamated rules correspond to the behavior rules from the classical translation approach.

Classical concurrency in the approach to graph rewriting, as defined by the shift equivalence construction [7], can also be represented by a graph process, a structure where concurrency and causal dependency are synthetically represented by a partial ordering of rewrites [1]. Interestingly, all shift equivalent derivations, considered as diagrams in the category of graphs, have the same colimit, which moreover exactly corresponds to the graph process. This construction, due to Corradini, Montanari and Rossi, was originally defined for rules with injective right-hand morphisms [6]. This condition turns out to be restrictive when graphs are used for modeling process calculi like ambients [4] or fusion [21], where the coalescing of read-only items is essential [11,13]. Recently, a paper by Habel, Müller and Plump [16] considered again shift equivalence, extending classical results to non-injective rules. In this paper we look at the graph-process-via-colimit approach: We propose and motivate its extension to non-injective rules in terms of existing computational models, and compare it with the aforementioned results.

Variables make rule-based systems more abstract and expressive, as witnessed by term rewriting systems and two-level grammars. In this paper we show that variables can be used to define advanced ways of graph transformation as well. Taking the gluing approach to graph transformation [7,3] as a basis, we consider extensions of rules with attribute variables, clone variables, and graph variables, respectively. In each case, the variables in a rule are instantiated in order to obtain a set of rule instances that in turn defines the transformation relation. By combining different kinds of variables, we define very expressive rules, and reduce them to plain rules by instantiation. Since gluing graph transformation has a well developed theory, this opens the door to lift results of that theory from instances to rules with variables.

In the beginning, one of the main fields of application of graph transformation was biology, and more specifically morphology. Later, however, it was like if the biological applications had been left aside by the graph transformation community, just to be moved back into the mainstream these very last years with a new interest in molecular biology. In this paper, we review several fields of application of graph grammars in molecular biology, including: the modelling of higher-dimensional structures of biomolecules, the description of biochemical reactions, and the study of biochemical pathways.

In the double-pushout approach to graph transformations, most authors assume the left-hand side to be injective, since the noninjective case leads to ambiguous results. Taking into consideration productions that change labels, however, may add ambiguity even in the case of injective graph productions. A well-known solution to this problem is restricting the categorical treatment to the underlying graphs, whereas the labels on the derived graph are defined by other means. In this paper, we resume the detailed results on arbitrary left-hand sides that Ehrig and Kreowski have already given in 1976. We apply these results to the case of relabeling such that we can retain the elegant categorical constructions at the level of labeled graphs.

A short personal note briefly traces the author’s interactions with Hartmut Ehrig. Where Ehrig has devoted much work to an algebraic theory of modules, the author has developed schema theory primarily as a tool for brain theory, but the author’s version of schema theory has also been associated with algebraic theory and robotics. Topics presented in the present informal overview of schema theory include the role of schemas in bridging from action-oriented perception to knowledge, the notion of schema instances and their role in cooperative computation, learning in schemas, and ways of linking schemas to the study of the brain.

In this paper, addressing the classical problem of modelling the behaviour of a system, we present a paradigmatic journey from purely formal and textual techniques to derived visual notations, with a further attention first to code generation and finally to the incorporation into a standard notation such as the UML.

We show how starting from positive conditional specifications with initial semantics of labelled transition systems, we can devise a new visual paradigm, the interaction charts, which are diagrams able to express both reactive and proactive/autonomous behaviour.

Then, we introduce the executable interaction charts, which are interaction charts with a special semantics, by which we try to ease the passage to code generation.

Finally, we present the interaction machines, which are essentially executable interaction charts in a notation that can be easily incorporated, as an extension, into the UML.