Fundamenta Informaticae - Volume 74, issue 1

Authors: Engels, Gregor | Orejas, Fernando | Parisi-Presicce, Francesco

Article Type: Other

Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. i-ii, 2006

Authors: Ehrig, Hartmut | Padberg, Julia | Prange, Ulrike | Habel, Annegret

Article Type: Research Article

Abstract: Adhesive high-level replacement (HLR) systems are introduced as a new categorical framework for graph transformation in the double pushout (DPO) approach, which combines the well-known concept of HLR systems with the new concept of adhesive categories introduced by Lack and Sobocinacute;ski. In this paper we show that most of the HLR properties, which had been introduced to generalize some basic results from the category of graphs to high-level structures, are valid already in adhesive HLR categories. This leads …to a smooth categorical theory of HLR systems which can be applied to a large variety of graphs and other visual models. As a main new result in a categorical framework we show the Critical Pair Lemma for the local confluence of transformations. Moreover we present a new version of embeddings and extensions for transformations in our framework of adhesive HLR systems. Show more

Keywords: high-level replacement systems, adhesive categories, adhesive HLR categories, graph transformation, local confluence of transformations, Critical Pair Lemma

Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 1-29, 2006

Authors: Ehrig, Hartmut | Ehrig, Karsten | Prange, Ulrike | Taentzer, Gabriele

Article Type: Research Article

Abstract: The concept of typed attributed graphs and graph transformation is most significant for modeling and meta modeling in software engineering and visual languages, but up to now there is no adequate theory for this important branch of graph transformation. In this article we give a new formalization of typed attributed graphs, which allows node and edge attribution. The first main result shows that the corresponding category is isomorphic to the category of algebras over a specific …kind of attributed graph structure signature. This allows to prove the second main result showing that the category of typed attributed graphs is an instance of "adhesive HLR categories". This new concept combines adhesive categories introduced by Lack and Sobociński with the well-known approach of high-level replacement (HLR) systems using a new simplified version of HLR conditions. As a consequence we obtain a rigorous approach to typed attributed graph transformation providing as fundamental results the Local Church-Rosser, Parallelism, Concurrency, Embedding and Extension Theorem and a Local Confluence Theorem known as Critical Pair Lemma in the literature. Show more

Keywords: typed attributed graph transformation, adhesive HLR categories, local confluence of transformations, Critical Pair Lemma

Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 31-61, 2006

Authors: Heckel, Reiko | Lajios, Georgios | Menge, Sebastian

Article Type: Research Article

Abstract: In distributed and mobile systems with volatile bandwidth and fragile connectivity, non-functional aspects like performance and reliability become more and more important. To formalize, measure, and predict such properties, stochastic methods are required. At the same time such systems are characterized by a high degree of architectural reconfiguration. Viewing the architecture of a distributed system as a graph, this is naturally modeled by graph transformations. To combine these two views, in this paper we …introduce stochastic graph transformation systems associating with each rule its application rate – the rate of the exponential distribution governing the delay of its application. Beside the basic definitions and a motivating example, we derive continuous time Markov chains, establish a link with continuous stochastic logic, deal with the problem of abstraction through graph isomorphisms, and discuss the analysis of properties by means of an experimental tool chain. Show more

Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 63-84, 2006

Authors: Chalopin, Jérémie | Métivier, Yves | Zielonka, Wiesław

Article Type: Research Article

Abstract: We examine the power and limitations of the weakest vertex relabelling system which allows to change a label of a vertex in function of its own label and of the label of one of its neighbours. We characterize the graphs for which two important distributed algorithmic problems are solvable in this model: naming and election.

Keywords: Distributed Computing, Local Computations, Election, Naming, Submersion

Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 85-114, 2006

Authors: Ehrenfeucht, Andrzej | Hage, Jurriaan | Harju, Tero | Rozenberg, Grzegorz

Article Type: Research Article

Abstract: In the context of graph transformation we look at the operation of switching, which can be viewed as a method for realizing global transformations of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient algorithms exist for deciding whether a graph can be switched so that it contains some other graph, the query graph, as an induced subgraph. However, when considering graphs up to isomorphism, we immediately run into …the graph isomorphism problem for which no efficient solution is known. Surprisingly enough however, in some cases the decision process can be simplified by transforming the query graph into a "smaller" graph without changing the answer. The main lesson learned is that the size of the query graph is not the dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected, unlabelled graphs, we propose a more general framework and give many positive and negative results for more general cases, where the graphs are labelled with elements of a (finitely generated abelian) group. Show more

Keywords: Seidel switching, graph algorithms, complexity, NP-completeness, embedding problem, cyclomatic number

Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 115-134, 2006

Authors: Ehrig, Hartmut | Ehrig, Karsten | Habel, Annegret | Pennemann, Karl-Heinz

Article Type: Research Article

Abstract: Graph constraints and application conditions are most important for graph grammars and transformation systems in a large variety of application areas. Although different approaches have been presented in the literature already there is no adequate theory up to now which can be applied to different kinds of graphs and high-level structures. In this paper, we introduce a general notion of graph constraints and application conditions and show under what conditions the basic results can be extended …from graph transformation to high-level replacement systems. In fact, we use the new framework of adhesive HLR categories recently introduced as combination of HLR systems and adhesive categories. Our main results are the transformation of graph constraints into right application conditions and the transformation from right to left application conditions in this new framework. The transformations are illustrated by a railroad control system with rail net constraints and application conditions. Show more

Keywords: graph transformation, constraints, application conditions, graphs, high-level structures, adhesive HLR categories

Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 135-166, 2006