Fundamenta Informaticae - Volume 58, issue 1

Authors: Corradini, Andrea | Kreowski, Hans-Jörg

Article Type: Other

Citation: Fundamenta Informaticae, vol. 58, no. 1, pp. i-ii, 2003

Authors: Gyapay, Szilvia | Varró, Dániel | Heckel, Reiko

Article Type: Research Article

Abstract: Following TER nets, an approach to the modeling of time in high-level Petri nets, we propose a model of time within (attributed) graph transformation systems where logical clocks are represented as distinguished node attributes. Corresponding axioms for the time model in TER nets are generalized to graph transformation systems and semantic variations are discussed. They are summarized by a general theorem ensuring the consistency of temporal order and casual dependencies. The resulting notions of typed graph …transformation with time specialize the algebraic double-pushout (DPO) approach to typed graph transformation. In particular, the concurrency theory of the DPO approach can be used in the transfer of the basic theory of TER nets. Show more

Keywords: graph transformation, time, concurrency

Citation: Fundamenta Informaticae, vol. 58, no. 1, pp. 1-22, 2003

Authors: Hage, Jurriaan | Harju, Tero | Welzl, Emo

Article Type: Research Article

Abstract: In the context of graph transformations we look at the operation of switching, which can be viewed as a method for realizing global transformations of graphs through local transformations of the vertices. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation. Continuing the line of research in Ehrenfeucht, Hage, Harju and Rozenberg we consider the problem of detecting three kinds of graphs in switching classes. …For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs. Show more

Keywords: Seidel switching, graph algorithms, complexity, NP-completeness

Citation: Fundamenta Informaticae, vol. 58, no. 1, pp. 23-37, 2003

Authors: Hoffmann, Berthold

Article Type: Research Article

Abstract: Shapely nested graph transformation is the computational model for DiaPlan, a language for programming with graphs representing diagrams that is currently being developed. The model supports nested structuring of graphs, structural graph types (shapes), and rules with graph variables. We extend this model by two concepts that are essential for programming: abstraction allows compound transformations to be named and parameterized; control allows the order of rule application to be specified. These concepts refine the …computational model with respect to structuring and efficiency needs of a programming language while preserving its rule-based and graph-ical nature. Show more

Keywords: graph, nested graph, diagram, graph typing, graph transformation, abstraction, control

Citation: Fundamenta Informaticae, vol. 58, no. 1, pp. 39-65, 2003